Cofactor canonicalisation of mpn_gcdext

Torbjorn Granlund tg at
Fri Nov 20 11:27:44 CET 2009

GMP 4.3 and earlier versions do not return the same cofactor from
mpn_gcdext (and as a consequence also from mpz_gcdext).

Assume we're computing g = us + vt, where g = gcd(u,v).

Earlier GMP versions seem to have computed s such that 0 <= 2|s| <= |v|/g.
For this to hold, s sometimes will be negative.

GMP 4.3 computes s,t that are much larger.  It is not completely clear
what the maximum values are.  We intend to tighten this.

What criteria should we apply?

We could follow the old GMP route of 0 <= 2|s| <= |v|/g, but it might be
better to instead promise 0 <= s <= |v|/g.  I.e., s is now non-negative.

We might also just promise the more lax 0 <= |s| <= |v|/g.

Please express any opinions you have about this as soon as possible.

Note that there are several considerations we need to take into account
here.  Functions in mpn are supposed to do just the work most callers
care about, and leave fine adjustments to callers that care.


More information about the gmp-devel mailing list