problem with NTL 5.5 when upgrading from GMP 4.2.4 to 4.3.0

[Torbjorn Granlund]

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
code.
  
  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.

True.
  
  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?

-- 
Torbjörn