expected behaviour of mpn_extgcd
Bill.Allombert at math.u-bordeaux1.fr
Wed Nov 4 11:28:37 CET 2009
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.
More information about the gmp-bugs