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