Cofactor canonicalisation of mpn_gcdext
tg at gmplib.org
Thu May 5 22:52:42 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> $ GMP_CHECK_RANDOMIZE=1498407732 tests/mpz/t-gcd
> Re-seeding with GMP_CHECK_RANDOMIZE=1498407732
> ERROR in test 142
> mpz_gcdext returned invalid result
> mpz_gcdext returns:
> Abort trap: 6
Does that mean that gcdext with inputs u = v = 0 gave the result gcd =
0, s = 1? Or am I misreading the output?
I don't remember off the top of my head what gcdext is supposed to
return in this corner case. I'll try to look into it in the next few
days, if no one else feels like fixing it earlier.
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.)
to make g = s*0 + t*0 be trye with our defined side conditions on s and
t, we need to set s=t=0.
I think this is actually not a memory corruption issue. Unlike all (?)
other test code, tests/mpz/t-gcd.c will *not* generate the same test
sequences for all platforms. The code uses some XXX_THRESHOLDs to
determine the sequence. I don't like this. (I wrote this code, btw.)
Anyway, the case u=v=0 as a result happens at different points in the
operand sequence, or not at all.
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.
More information about the gmp-devel