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 
  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 mailing list