Extended GCP in public key crypto

#유클리드 알고리즘
def gcd(a, b):
    if b == 0: #만약 b가 0이라면 a가 gcd
        return a
    else: #b가 0이 아니라면 정수배 선형결합을 한 값을 주고 재귀
        return gcd(b, a%b)

#확장 유클리드 알고리즘
def extended_gcd(a, b):
    r0, r1 = a, b #초기 r0, r1값 초기화
    x0, y0 = 1, 0 #초기 x0, y0값 초기화
    x1, y1 = 0, 1 #초기 x1, y1값 초기화
    gcd_value = gcd(a, b) #gcd값을 추출
    while gcd_value != r1: #r1이 gcd에 도달할 때까지
        x0, y0, x1, y1 = x1, y1, x0-(r0//r1)*x1, y0-(r0//r1)*y1
        #확장 유클리드 알고리즘에 의한 다음 x, y값 초기화
        r0, r1 = r1, r0%r1
        #다음 q값(r0//r1)을 얻기 위한 초기화
        #print('{} = {}*{} + {}*{}'.format(r1, a, x1, b, y1))
        #계산이 올바르게 수행되는지 확인하기 위한 출력
    return x1, y1 #x, y값 반환

#결과가 올바르게 나왔는지 확인하는 함수
def verify(x, y, d, a, b):
    if d == a*x + b*y: #올바르게 구했다면 Correct 출력
        print("Correct")
    else: #올바르지 않다면 Wrong 출력
        print("Wrong")

#해를 구하고자 하는 방정식의 출력함수
def printans(a, b, num):
    egcd_x, egcd_y = extended_gcd(a, b) #x, y값 초기화
    print(num+") ({}, {})".format(egcd_x, egcd_y)) #출력
    verify(egcd_x, egcd_y, gcd(a, b), a, b) #올바른지 확인


print("-----answer form: (x, y) => ax + by = d-----")
printans(45, 78, "a")
printans(666, 1428, "b")
printans(1020, 10290, "c")
printans(2 ** 20 + 4, 3 ** 10 + 5, "d")
printans(2 ** 30 + 1, 3 ** 30 + 6, "e")
'''
printans(1180, 482, "test1")
printans(240, 46, "test2")
'''

 

#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM * a)
{
        char * number_str = BN_bn2dec(a);
        printf("%s %s\n", msg, number_str);
        OPENSSL_free(number_str);
}

BIGNUM *XEuclid(BIGNUM *x, BIGNUM *y, const BIGNUM *a, const BIGNUM *b)
{
	BN_CTX *ctx = BN_CTX_new();
  	BIGNUM *r = BN_new();
  	BIGNUM *a_copy = BN_new();
  	BIGNUM *b_copy = BN_new();
  	BN_copy(a_copy, a);
  	BN_copy(b_copy, b);
  	while (!BN_is_zero(b_copy))
  	{
		if(!BN_mod(r,a_copy,b_copy,ctx))
			return NULL;
		BN_copy(a_copy,b_copy);
		BN_copy(b_copy,r);
  	}
  	BN_copy(r,a_copy);
  	BN_free(a_copy); BN_free(b_copy);

  	BIGNUM *x0 = BN_new(); BIGNUM *x1 = BN_new(); BIGNUM *x_copy = BN_new();
  	BIGNUM *y0 = BN_new(); BIGNUM *y1 = BN_new(); BIGNUM *y_copy = BN_new();
  	BIGNUM *r0 = BN_new(); BIGNUM *r1 = BN_new(); BIGNUM *r_copy = BN_new();
  	BIGNUM *tx = BN_new(); BIGNUM *ty = BN_new();
  	BIGNUM *dv = BN_new(); BIGNUM *rem = BN_new();
  	BN_dec2bn(&x0, "1"); BN_dec2bn(&y0, "0"); 
	BN_dec2bn(&x1, "0"); BN_dec2bn(&y1, "1");
	BN_copy(r0, a); BN_copy(r1, b);
	while(BN_cmp(r, r1))
	{
		BN_copy(tx, x1); BN_copy(ty, y1);
		if(!BN_div(dv, rem, r0, r1, ctx))
			return NULL;
		if(!BN_mul(x_copy, dv, x1, ctx))
			return NULL;
		BN_sub(x1, x0, x_copy);
		if(!BN_mul(y_copy, dv, y1, ctx))
			return NULL;
		BN_sub(y1, y0, y_copy);
		BN_copy(x0, tx); BN_copy(y0, ty);
		BN_copy(r_copy, r1);
		if(!BN_mod(r1, r0, r1, ctx))
			return NULL;
		BN_copy(r0, r_copy);
	}
	BN_copy(x, x1);
	BN_copy(y, y1);
	if(ctx != NULL)
  		BN_CTX_free(ctx);
  	BN_free(x0); BN_free(x1); BN_free(x_copy);
  	BN_free(y0); BN_free(y1); BN_free(y_copy);
  	BN_free(r0); BN_free(r1); BN_free(r_copy);
  	BN_free(tx); BN_free(ty); BN_free(dv); BN_free(rem);
	return r;
}

int main (int argc, char *argv[])
{
	BIGNUM *a = BN_new();
	BIGNUM *b = BN_new();
	BIGNUM *x = BN_new();
	BIGNUM *y = BN_new();
	BIGNUM *gcd;
	
	if(argc != 3){
		printf("usage: xeuclid num1 num2");
		return -1;
	}

	BN_dec2bn(&a, argv[1]);
	BN_dec2bn(&b, argv[2]);
	
	gcd = XEuclid(x,y,a,b);
	
	printBN("(a,b) = ", gcd);
	printBN("a = ", a);
	printBN("b = ", b);
	printBN("x = ", x);
	printBN("y = ", y);
	printf("%s*(%s) + %s*(%s) = %s\n",BN_bn2dec(a),BN_bn2dec(x),BN_bn2dec(b),BN_bn2dec(y),BN_bn2dec(gcd));

	if(a != NULL) BN_free(a);
	if(b != NULL) BN_free(b);
	if(x != NULL) BN_free(x);
	if(y != NULL) BN_free(y);
	if(gcd != NULL) BN_free(gcd);
	return 0;
}