problem with NTL 5.5 when upgrading from GMP 4.2.4 to 4.3.0

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

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

I thought a little about this when writing the new gcdext code. I may
have forgotten some details, but I used the following interface for
gcdext_1, uniquely determining the choice of cofactors:

  /* FIXME: Takes two single-word limbs. It could be extended to a
   * function that accepts a bignum for the first input, and only
   * returns the first co-factor. */
  
  /* Returns g, u and v such that g = u A - v B. There are three
     different cases for the result:
  
       g = u A - v B, 0 < u < b, 0 < v < a
       g = A          u = 1, v = 0
       g = B          u = B, v = A - 1
  
     We always return with 0 < u <= b, 0 <= v < a.
  */
  
  static mp_limb_t
  gcdext_1_odd (mp_limb_t *up, mp_limb_t *vp, mp_limb_t a, mp_limb_t b)
  { ... }

I don't remember why I settled on 0 < u <= B rather than 0 <= u < B,
maybe there's no good reason.

Anyway, I think it would make a lot of sense to use the same
inequalities for the general gcdext function, but I'm not sure if
there are any complications to implementing that.

For the documentation, I think we settled for the bound |u| <= B,
which leaves some freedom to the implementation.

/Niels