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