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

[marco.bodrato at tutanota.com]

Ciao Niels,

17 feb 2024, 17:53 da nisse at lysator.liu.se:

> Niels Möller <nisse at lysator.liu.se> writes:
> The documented conditions say that gmp should return the same cofactors
>

The documentation also says "If abs(a) = abs(b), then s = 0, t = sgn(b)."


>
> canonicalization logic at the end wasn't right. Appending a patch with a
> fix + stricter tests.
>

And if I correctly patched and tested your proposed code. with equal numbers I get t=0, instead of s=0.


> Without the fix, we could make the wrong choice in case
>
>  |s'| = |s| = |b| / 2g
>
> Since it's a bit subtle, it would be nice with a review of this code
> before I commit it.
>

Shat about simply changing the test from > to >= ?

   /* Arrange so that |s| < |u| / 2g */
   mpz_add (s1, s0, s1);
-  if (mpz_cmpabs (s0, s1) > 0)
+  if (mpz_cmpabs (s0, s1) >= 0)
     {
       mpz_swap (s0, s1);
       mpz_sub (t0, t0, t1);

Ĝis,
m