problem with NTL 5.5 when upgrading from GMP 4.2.4 to 4.3.0

[Paul Zimmermann]

       Hi,

thanks to Torbjörn 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.

Paul Zimmermann

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.