expected behaviour of mpn_extgcd
Torbjorn Granlund
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
mpn_gcdext(1230460696535801497442995200,9095580234321003098716589834342400)
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.
--
Torbjörn
More information about the gmp-bugs
mailing list