bn_gcd_ext_binar returns different Bezout coefficients

[guidovranken]

Assuming that for every given A, B bn_gcd_ext_binar must return the same Bezout coefficients X, Y as bn_gcd_ext, which satisfy X <= (B / (2 * GCD(A,B))) and Y <= (A / (2 * GCD(A,B))), the following code provides a counterexample for which this does not hold.

See also #223

#include <relic.h>

static void print(const bn_t bn) {
    const size_t size = bn_size_str(bn, 10);
    char* s = malloc(size);
    bn_write_str(s, size, bn, 10);
    printf("%s\n", s);
    free(s);
}

static void test(const char* s1, const char* s2, const int binar) {
    bn_t A, B, R1, R2, R3;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(R1); bn_new(R1);
    bn_null(R2); bn_new(R2);
    bn_null(R3); bn_new(R3);

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    printf("A: ");
    print(A);
    printf("B: ");
    print(B);
    if ( binar == 0 ) {
        printf("bn_gcd_ext:\n");
        bn_gcd_ext(R1, R2, R3, A, B);
    } else {
        printf("bn_gcd_ext_binar:\n");
        bn_gcd_ext_binar(R1, R2, R3, A, B);
    }
    printf("GCD: ");
    print(R1);
    printf("X: ");
    print(R2);
    printf("Y: ");
    print(R3);
    printf("\n");

    bn_free(A);
    bn_free(B);
    bn_free(R1);
    bn_free(R2);
    bn_free(R3);
}

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    test("132932242323", "18", 0);
    test("132932242323", "18", 1);

    test("800000000000007", "6", 0);
    test("800000000000007", "6", 1);

    return 0;
}

This prints:

A: 132932242323
B: 18
bn_gcd_ext:
GCD: 9
X: 1
Y: -7385124573

A: 132932242323
B: 18
bn_gcd_ext_binar:
GCD: 9
X: -1
Y: 7385124574

A: 800000000000007
B: 6
bn_gcd_ext:
GCD: 3
X: 1
Y: -133333333333334

A: 800000000000007
B: 6
bn_gcd_ext_binar:
GCD: 3
X: -1
Y: 133333333333335

Validate Bezout coefficients in Python:

def T(A, B, X, Y, GCD):
    GCDx2 = GCD * 2
    assert(A*X + B*Y == GCD)

    assert(X <= B // GCDx2)
    assert(Y <= A // GCDx2)

# bn_gcd_ext
# OK
T(132932242323, 18, 1, -7385124573, 9)
# OK
T(800000000000007, 6, 1, -133333333333334, 3)

# bn_gcd_ext_binar
# Fail
T(132932242323, 18, -1, 7385124574, 9)
# Fail
T(800000000000007, 6, -1, 133333333333335, 3)

[dfaranha]

Thank you for reporting! It looks like my fix for #223 was incomplete and 554cb0f should fix it. :)

[guidovranken]

Confirmed fixed.