expected behaviour of mpn_extgcd

[Bill Allombert]

On Fri, Oct 09, 2009 at 08:01:40AM +0200, Torbjorn Granlund wrote:
> Bill Allombert <Bill.Allombert at math.u-bordeaux1.fr> writes:
> 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.

(sorry if I make it appears like there was a bug in gmp)

I would like this issue to be resolved soon if possible, because currently
no PARI/GP versions work correctly with GMP 4.3.

I tried to fix the issue in PARI/GP but this is hard to do efficiently without
some clear limit on what cofactors GMP can return.

Basically there are two use-cases for mpn_extgcd:
1) modular inversion of a mod b: in that case the GCD is assumed to be 1,
and v is not used. If u is too large, it is sufficient to reduce it modulo
b. Realistically mpn_extgcd cannont be allowed to return cofactors that are
much larger than the input, so we can assume that u is not much larger than b.

2) full case: We need u, v and d. We need to compute
b/d and reduce u modulo b/d. Note that this requires the computation of
b/d even if u was already reduced, and there is no a priori reasons for
u to be of the order of b/d. 

Cheers,
Bill.