Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at lysator.liu.se
Mon Nov 23 14:23:22 CET 2009

abbott <abbott at dima.unige.it> writes:

> I didn't know it either but it can be proved,
> see Theorem 4.3(vi) page 78 in Shoup's book:
>     http://www.shoup.net/ntb/

It almost spells out the result we're talking about. Part (v) says, in
our notation:

|t| <= u / r_{\lambda-1}, |s| <= v / r_{\lambda-1}

where

r_{\lambda-1} = r_\lambda q_\lambda = g q_\lambda

is the last-but-one nonzero remainder in the remainder sequence.

So equality, |t| = u / g or |s| = v/g, is not ruled out, as far as I
see. When does that happen, and which border is hit? When v/g is even,
one could choose between the ranges

-v/g <= 2s <= v/g - 2

and

-v/g + 2 <= 2s <= v/g

Which range does the values returned by Euclid's algorithm fit in?
Does it matter in the context of GMP?

For which inputs can we really require that 2 |s| < v/g, with *strict*
inequality?

Regards,
/Niels
{"ft_lang_label":"__label__en","ft_lang_prob":0.86121327,"math_prob":0.95626354,"size":1004,"snap":"2022-05-2022-21","text_gpt3_token_len":328,"char_repetition_ratio":0.089,"word_repetition_ratio":0.0,"special_character_ratio":0.3187251,"punctuation_ratio":0.13452914,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9881976,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-23T05:36:52Z\",\"WARC-Record-ID\":\"<urn:uuid:7bba39fa-5ee5-4907-b155-5e3af6e5018d>\",\"Content-Length\":\"3516\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:18c7ded6-13b9-4a84-ba4b-4b7ab399af23>\",\"WARC-Concurrent-To\":\"<urn:uuid:f530facb-6435-441e-9914-0746177769f5>\",\"WARC-IP-Address\":\"130.242.124.102\",\"WARC-Target-URI\":\"https://gmplib.org/list-archives/gmp-devel/2009-November/001215.html\",\"WARC-Payload-Digest\":\"sha1:F2BEQQV3C5423PDHF6XONNKWVSSRICC2\",\"WARC-Block-Digest\":\"sha1:ELPJ5ZYROZBFDDSEHLWYVDKDE2NLQTJB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320304134.13_warc_CC-MAIN-20220123045449-20220123075449-00650.warc.gz\"}"}