# problem with NTL 5.5 when upgrading from GMP 4.2.4 to 4.3.0

Niels Möller nisse at lysator.liu.se
Sat Apr 25 20:05:47 CEST 2009

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

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