expected behaviour of mpn_extgcd

[Torbjorn Granlund]

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