Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at
Sun May 8 17:15:54 CEST 2011

Torbjorn Granlund <tg at> writes:

> One usually defines gcd(a,0) = |a|.  (But it seems that for a=0, one may
> define gcd as any positive integer, while 0 is a poor divisor.)

I mathematics, I think gcd(0,0) is usually undefined. As far as I can
find, not even Knuth defines a value the gcd function in this case. If
we don't want to raise a divide-by-zero error, I guess 0 is a reasonable
value to return (for lack of a representation of infinity).

> This code from mpz/gcdext.c looks suspicious:
>         /* g = |a|, s = sign(a), t = 0. */
>         ssize = SIZ (a) >= 0 ? 1 : -1;
> Since a = 0 is possible here, this is a poor computation of sgn(a).
> I pushed a fix.  I also made some other minor tweaks.

I see. I totally forgot normalization for the a == b == 0 case.

Maybe the sentence "S = 0 if and only if V divides U (i.e., G = V)." in
the docs need a tweak? Actually, behaviour for both inputs zero seem to
be completely undocumented.

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

More information about the gmp-devel mailing list