expected behaviour of mpn_extgcd

Bill Allombert Bill.Allombert at math.u-bordeaux1.fr
Fri Oct 9 09:47:21 CEST 2009

On Fri, Oct 09, 2009 at 08:01:40AM +0200, Torbjorn Granlund wrote:
> 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.

Really sorry for the typo and failing to attach the test-case, I meant v=1
of course (but anyway, mpn_gcdext does not return v). The test-case use
mpz_gcdext while PARI use mpn_gcdext but both return the same result.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: bug.c
Type: text/x-csrc
Size: 429 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-bugs/attachments/20091009/36151916/attachment.bin>

More information about the gmp-bugs mailing list