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

Niels Möller nisse at
Sat Feb 17 21:26:31 CET 2024

marco.bodrato at writes:

> Maybe we should also add the test:
>   /* Require that s==0 iff g==abs(b) */
>   if (!mpz_sgn (s) ^ !mpz_cmpabs (g, b))
>       goto fail;

Good point, that's better than only checking the special case |a| ==
|b|. (But maybe more readable with != instead of ^).

To get mini-gmp to conform, I find no simpler way than special casing s
== 0, like

  if (mpz_sgn (s0) != 0)
      /* Arrange so that |s| < |u| / 2g and |t| < |v| / 2g, if possible. */
      mpz_add (s1, s0, s1);
      mpz_sub (t1, t0, t1);
      if (mpz_cmpabs (s0, s1) > 0 || mpz_cmpabs (t0, t1) > 0)
	  mpz_swap (s0, s1);
	  mpz_swap (t0, t1);

And I think this is the only condition that isn't fully symmetrical, so
perhaps not surprising if it needs a special case.


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

More information about the gmp-bugs mailing list