expected behaviour of mpn_extgcd
tg at gmplib.org
Fri Oct 9 08:01:40 CEST 2009
Bill Allombert <Bill.Allombert at math.u-bordeaux1.fr> writes:
Dear GMP developers,
GMP function mpn_gcdext(a,b) used to return the smallest u in absolute value
such that a*u+b*v=d. This is no more the case in version 4.3, for example for
we expect u=1,v=0 since a divides b, but we get u=-7392011, v=0.
and unfortunately this change breaks PARI/GP.
If that's what GMP returns, a*u+b*v=gcd(a,b) does not hold.
That would be a serious bug.
Please send us a comlete bug report, i.e., with test case etc.
The GMP manual explains what information is needed.
Is this change intentional ? In that case, could the documentation clarify
what values for u are acceptable ? (The documentation terms "u" '_The_ first
cofactor' (emphasis mine) which somehow induce a French reader to expect it to
be uniquely defined. We are taught that way...).
There have been a change in the cofactor returned, but the above
equation should hold.
Perhaps we should return more canonical cofactor values to,
but let's address the bug first.
More information about the gmp-bugs