Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> You should should ask the GMP GCD code developer, I recommend a chat to
> your bathroom mirror.  :-)

According to NEWS, the new gcdext code was released in gmp-4.3.
gmp-4.2.4 definitely use the old code. And my mirror image has a very
bad memory for such things.

>   * The documentation said the needed size for gp and sp is given by the
>     size of the larger input, un (or un+1 for the pre 4.3 versions). I
>     think this was a typo, and that it's always been given by the smaller
>     input vn (or vn+1 in pre 4.3 versions), so I changed this. Correct?
>   
> I think you're wrong.  I find it unwise to make such a change unless you
> find support for your assumption in old GMP code.

Both the current code and the mpn_gcdext in gmp-4.2.4 starts with
something like

  if (un > vn)
    mpn_tdiv_qr (tp, up, up, 0, up, un, vp, vn);

and discards the quotient. After this, all inputs are of size vn. I
really find it difficult to imagine why it would generate outputs (or
temporaries, except for the initial and ignored quotient above) of more
than vn limbs.

mpz_gcdext still allocates un limbs for both gp and sp (and did allocate
un+1 until my checkin yesterday). I'll try reducing that to vsize, to
see what happens (and gsize == usize actually happens in the case vsize
== 0, which is allowed by mpz_gcdext but not by mpn_gcdext).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.