Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at
Tue Nov 24 15:18:42 CET 2009

abbott <abbott at> writes:

> Torbjörn> At the mpn level, we might choose not to pin things down for degenerate
> Torbjörn> cases, unless it can be done for free.

I think whatever part of this discussion should not be applied to
mpn_gcdext, should probably be applied to mpz_gcdext instead.

> Maybe the degenerate input (0,0) should be handled specially?

At the mpn level, zero inputs to the gcd functions are not allowed at all.

> I think that specifying  s = 0  when  u = v  will give the simplest code
> (if the underlying implementation follows Shoup's definition of EA).

It seems nice to have s = 0 iff v divides u, including the case u = v.

Another interface detail is whether or not one should require that u
>= v, or only that limb count(u) >= limb count (v). The current
documentation specifies different input requirements for mpn_gcd and
mpn_gcdext, matching the needs of previous implementations.


More information about the gmp-devel mailing list