problem with NTL 5.5 when upgrading from GMP 4.2.4 to 4.3.0
tg at gmplib.org
Sat Apr 25 14:07:49 CEST 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
thanks to Torbjörn's hint about mpn_gcdext, I was able to isolate the problem.
At some point, LLLTest calls mpn_gcdext with inputs s1=4 and s2=2. GMP 4.2.4
returns r1=2 (r1 is the gcd) and r2=0, which satisfies r2*s1+k*s2=r1,
where here k=1.
GMP 4.3.0 returns r1=2 too, but r2=1, which also satisfies r2*s1+k*s2=r1,
but with k=-1. If I then change r2 to 0 in the NTL code for this particular
case, the LLLTest produces the desired (expected) output.
Now maybe the different matrix returned with GMP 4.3.0 is still reduced,
and thus is a valid output. I let Victor Shoup check that.
In summary: no GMP bug.
We should probably have pointed out this change in the release notes,
since it is bound to cause some problems, at least with overstrict test
PS: this raises the following question: is there a way to uniquely define the
cofactors of the extended gcd a*x + b*y = g, assuming x, y, g > 0? Since
(a-y)*x + (b+x)*y = g, we can for example force 0 <= b < x, or -x/2 < b <= x/2.
Unless I am mistaken, this also shows that there is no need to have a sign for
r2 in mpn_gcdext, since we can force 0 <= r2 < s2.
We also have (a-y/g)*x + (b+x/g)*y = g, thus we can even force 0 <= b < x/g,
where g = gcd(x,y). In the above example this would give 0 <= r2 < 1, thus
the output would be that given by GMP 4.2.4.
We had discussions about this internally some while ago, but I don't
recall if we came to a firm conclusion.
Should we slow down the code a little and get a more strictly bounded
cofactor value for the price? The price is small, but if the operands
are just a few limbs, it might still hurt.
I assume the new GMP 4.3 code could actually produce different cofactor
value depending on which algorithm is being used, as determined by
GCDEXT_DC_THRESHOLD. Niels, is that true?
More information about the gmp-bugs