Niels Möller <ni...@lysator.liu.se> writes: > Guido Vranken <guidovran...@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 documented conditions say that gmp should return the same cofactors as one would get naturally with Euclid's algorithm. It appears mini-gmp uses binary gcdext (I had forgotten that detail), and the canonicalization logic at the end wasn't right. Appending a patch with a fix + stricter tests. At this place in the algorithm, we have a, b >= 0, and we have a candidate s, t, with -b / g <= s <= 0, 0 <= t <= a / g (not sure at which edges we might have equality), and then we construct another candidate s', t' as s' = s + b / g >= 0, t' = t - a / g <= 0 And we then return s', t' if either |s'| < |s| or |t'| < |t|. 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. Regards, /Niels diff -r 1c566525476a mini-gmp/mini-gmp.c --- a/mini-gmp/mini-gmp.c Wed Dec 27 19:35:36 2023 +0100 +++ b/mini-gmp/mini-gmp.c Sat Feb 17 17:17:21 2024 +0100 @@ -2960,12 +2960,13 @@ mpz_tdiv_q_2exp (t0, t0, 1); } - /* Arrange so that |s| < |u| / 2g */ + /* Arrange so that |s| < |u| / 2g and |t| < |v| / 2g, if possible. */ mpz_add (s1, s0, s1); - if (mpz_cmpabs (s0, s1) > 0) + mpz_sub (t1, t0, t1); + if (mpz_cmpabs (s0, s1) > 0 || mpz_cmpabs (t0, t1) > 0) { mpz_swap (s0, s1); - mpz_sub (t0, t0, t1); + mpz_swap (t0, t1); } if (u->_mp_size < 0) mpz_neg (s0, s0); diff -r 1c566525476a mini-gmp/tests/t-gcd.c --- a/mini-gmp/tests/t-gcd.c Wed Dec 27 19:35:36 2023 +0100 +++ b/mini-gmp/tests/t-gcd.c Sat Feb 17 17:17:21 2024 +0100 @@ -79,20 +79,20 @@ if (mpz_sgn (r) != 0) goto fail; - /* Require that 2 |s| < |b/g|, or |s| == 1. */ - if (mpz_cmpabs_ui (s, 1) > 0) + /* Require that 2 |s| < |b/g|, or s == sgn(a) */ + if (mpz_cmp_si (s, mpz_sgn (a)) != 0) { mpz_mul_2exp (r, s, 1); - if (mpz_cmpabs (r, tb) > 0) + if (mpz_cmpabs (r, tb) >= 0) goto fail; } - /* Require that 2 |t| < |a/g| or |t| == 1*/ - if (mpz_cmpabs_ui (t, 1) > 0) + /* Require that 2 |t| < |a/g| or t == sgn(b) */ + if (mpz_cmp_si (t, mpz_sgn (b)) != 0) { mpz_mul_2exp (r, t, 1); - if (mpz_cmpabs (r, ta) > 0) - return 0; + if (mpz_cmpabs (r, ta) >= 0) + goto fail; } mpz_clear (ta); @@ -102,17 +102,53 @@ return 1; } +static void test_one(const mpz_t a, const mpz_t b) +{ + mpz_t g, s, t; + + mpz_init (g); + mpz_init (s); + mpz_init (t); + + mpz_gcdext (g, s, t, a, b); + if (!gcdext_valid_p (a, b, g, s, t)) + { + fprintf (stderr, "mpz_gcdext failed:\n"); + dump ("a", a); + dump ("b", b); + dump ("g", g); + dump ("s", s); + dump ("t", t); + abort (); + } + + mpz_gcd (s, a, b); + if (mpz_cmp (g, s)) + { + fprintf (stderr, "mpz_gcd failed:\n"); + dump ("a", a); + dump ("b", b); + dump ("r", g); + dump ("ref", s); + abort (); + } + + mpz_clear (g); + mpz_clear (s); + mpz_clear (t); +} + void testmain (int argc, char **argv) { unsigned i; - mpz_t a, b, g, s, t; + mpz_t a, b, g, s; + int ai, bi; mpz_init (a); mpz_init (b); mpz_init (g); mpz_init (s); - mpz_init (t); for (i = 0; i < COUNT; i++) { @@ -129,6 +165,15 @@ } } + /* Exhaustive test of small inputs */ + for (ai = -30; ai <= 30; ai++) + for (bi = -30; bi <= 30; bi++) + { + mpz_set_si (a, ai); + mpz_set_si (b, bi); + test_one (a, b); + } + for (i = 0; i < COUNT; i++) { unsigned flags; @@ -147,32 +192,11 @@ if (flags & 2) mpz_neg (b, b); - mpz_gcdext (g, s, t, a, b); - if (!gcdext_valid_p (a, b, g, s, t)) - { - fprintf (stderr, "mpz_gcdext failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("g", g); - dump ("s", s); - dump ("t", t); - abort (); - } + test_one (a, b); + } - mpz_gcd (s, a, b); - if (mpz_cmp (g, s)) - { - fprintf (stderr, "mpz_gcd failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", g); - dump ("ref", s); - abort (); - } - } mpz_clear (a); mpz_clear (b); mpz_clear (g); mpz_clear (s); - mpz_clear (t); } diff -r 1c566525476a tests/mpz/t-gcd.c --- a/tests/mpz/t-gcd.c Wed Dec 27 19:35:36 2023 +0100 +++ b/tests/mpz/t-gcd.c Sat Feb 17 17:17:21 2024 +0100 @@ -440,8 +440,8 @@ if (mpz_sgn (temp3) != 0) return 0; - /* Require that 2 |s| < |b/g|, or |s| == 1. */ - if (mpz_cmpabs_ui (s, 1) > 0) + /* Require that 2 |s| < |b/g|, or s == sgn(a) */ + if (mpz_cmp_si (s, mpz_sgn (a)) != 0) { mpz_mul_2exp (temp3, s, 1); if (mpz_cmpabs (temp3, temp2) >= 0) @@ -456,8 +456,8 @@ if (mpz_sgn (temp3) != 0) return 0; - /* Require that 2 |t| < |a/g| or |t| == 1*/ - if (mpz_cmpabs_ui (temp2, 1) > 0) + /* Require that 2 |t| < |a/g| or t == sgn(b) */ + if (mpz_cmp_si (temp2, mpz_sgn (b)) != 0) { mpz_mul_2exp (temp2, temp2, 1); if (mpz_cmpabs (temp2, temp1) >= 0) -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs