bn_gcd_ext_binar returns different Bezout coefficients #287
Description
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)