mini-gmp mpz_gcdext Bézout coefficients do not match documentation
Guido Vranken
guidovranken at gmail.com
Sat Feb 17 04:51:17 CET 2024
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
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 <=)
Then, for libgmp this is true: s: 1 <= 4 / 4, t: 1 <= 6 / 4
For mini-gmp this is false for t: s: 1 <= 4 / 4, t: 2 <= 6 / 4
Reproducer:
//#include <gmp.h>
#include "mini-gmp.c"
#include <stdio.h>
static void test(
const unsigned long int a_ui,
const unsigned long int b_ui)
{
mpz_t a, b, g, s, t;
mpz_init(a);
mpz_init(b);
mpz_init(g);
mpz_init(s);
mpz_init(t);
mpz_set_ui(a, a_ui);
mpz_set_ui(b, b_ui);
mpz_gcdext(g, s, t, a, b);
printf("g: %s, s: %s, t: %s\n",
mpz_get_str(NULL, 10, g),
mpz_get_str(NULL, 10, s),
mpz_get_str(NULL, 10, t));
}
int main()
{
test(1, 2);
test(6, 4);
}
Tested on Linux x64 using the latest repository code.
More information about the gmp-bugs
mailing list