mini-gmp mpz_gcdext Bézout coefficients do not match documentation

[Niels Möller]

Guido Vranken <guidovranken at gmail.com> writes:

> Computing extended gcd using mpz_gcdext where a = 1, b = 2:
>
> libgmp: g: 1, s: 1, t: 0
> mini-gmp: g: 1, s: -1, t: 1
> This violates the docs: "s = sgn(a) if abs(b) = 2", e.g. s must be 1
>
> Computing extended gcd using mpz_gcdext where a = 6, b = 4:
> libgmp: g: 2, s: 1, t: -1
> mini-libgmp: g: 2, s: -1, t: 2

I think mini-gmp is wrong here, I'll have to investigate. Thanks for
reporting.

> The docs state: "abs(s) < abs(b) / (2 g) and abs(t) < abs(a) / (2 g)"
> I think that should be: "abs(s) <= abs(b) / (2 g) and abs(t) <= abs(a) / (2
> g)"
> (< should be <=)

These strict equalities don't hold for the documented "exceptional"
cases. IT seems both your examples have abs(B) = 2G, so that's the case
that applies.

It is a bit subtle. And even if one relaxes the inequalities as you
suggest, 1 = gcd(1,1) would still be an exception (since in that case,
we'd get |s|, |t| < 1/2, i.e., s = t = 0, which isn't reasonable).

Can you suggest any doc change to make it clearer?

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.