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.
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
More information about the gmp-bugs
mailing list