Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Should we perhaps keep a compatibility note in the documentation, since
> lean allocation in applications will introduce nasty buffer overrun bugs,
> if linked to GMP 4.3 or older?

Maybe. If so, a similar note should be added to mpn_gcd (it also used to
destroy inputs plus an extra limb, right)?

> Perhaps mpz_gcdext (or some mpn_gcdext2) could perform an initial step
> (i.e., division) for this case, to avoid adding overhead to mpn_gcdext?

That was my first thought too, but it's not so easy, I'm afraid. Say U <
V, and we first divide

  V = Q U + V'

Then call mpn_gcdext on U, V', so that

  G = S' U + T' V' (where T' is implicit)

Then the needed cofactor is

  S = S' - Q T' (an addition, since S' and T' have opposite signs)

So we'd still have to compute the implicit T' (which can be expected to
be of size roughly sn - qn),

So I think this mehod might make sense for the case that V is much larger
than U, but for U and V of roughly the same size, I think it will be
faster to compute S directly, using Q to initiale the cofactor variable.

Regards,
/Niels

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