< 암호학 > 확장 유클리드 알고리즘

확장 유클리드 알고리즘이란?

두 수의 최대공약수를 구하는 과정에서 , 베주 항등식(Bézout's Identity) 계수인 x와 y를 찾는 알고리즘입니다.

 

즉, 기본 유클리드 알고리즘에서 나머지 연산을 반복하면서, 동시에 계수 x와 y를 추적하여 베주 항등식을 만족하는 값을 찾고,

이를 모듈로 역원을 구하는 데 사용합니다. 

 

베주 항등식

두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식입니다.

GCD(a,b) = ax + by = d

위 방정식은 다음과 같은 의미를 가집니다.

적어도 둘 중 하나는 0이 아닌 정수 a,b가 있고 그 최대공약수를 d라 합니다.

 

이때 다음 세 명제가 성립합니다.

1. d = ax + by를 만족하는 정수 x,y가 반드시 존재한다.

2. d는 정수 x,y에 대하여 ax+by 형태로 표현할 수 있는 가장 작은 자연수이다.

3. 정수 x,y에 대하여 ax+by 형태로 표현되는 모든 정수는 d의 배수이다. 

 

확장 유클리드 알고리즘 설명

gcd(a,b)

= gcd(b, a%b)

= gcd (a%b, b% (a%b))

= ...

= gcd (d,0) = d = ax + by   

를 이용합니다.

 

.

 

d0 = a = a*x0 + b*y0 : x0 = 1, y0 = 0 (초기값)

d1 = b = a*x1 + b*y1 : x1 = 0, y1 = 1 (초기값)

초기 x0, x1, y0, y1은 고정입니다.

 

d2 = d0 - (d0/d1)*d1 = a*x2 + b*y2

d3 = d1 - (d1/d2)*d2 = a*x3 + b*y3

...

 

일반화하자면,

 

반복 종료

 

유클리드 /  확장 유클리드 c 언어 구현

// 유클리드
int gcd(int a, int b) {
    int temp = 0;  
    while (b != 0) { 
        temp = b;  
        b = a % b;  
        a = temp;  
    }
    return a;  // b가 0이 돼서 while을 탈출한 경우, a가 최대공약수
}

// 확장 유클리드
int xgcd(int a, int b, int *x, int *y) {
    if (b == 0) {  // b가 0이면 최대공약수는 a, x는 1, y는 0
        *x = 1;  
        *y = 0;  
        return a;  
    }

    int x1, y1;  
    int gcd = xgcd(b, a % b, &x1, &y1);  // 재귀 호출로 gcd를 계산

    *x = y1;  // x 값을 업데이트 (이전 단계의 y1을 사용)
    *y = x1 - (a / b) * y1;  

    return gcd; 
}

 

 

모듈로 역원

모듈로 역원은 두 수가 서로소일 때 존재합니다. 두 수가 서로소라는 것은 최대공약수가 1이라는 뜻입니다.

따라서 위 확장유클리드 과정을 거친 후,

최대 공약수가 1이라면, 그때의 계수가 해당하는 값의 모듈로 역원이 됩니다.

다음과 같습니다.

 

ax + by의 최대공약수를 구한 값이 1이기 때문에 a와 b가 서로소입니다.

그때의 a의 mod m 역원 ( b = m )을 구하는 과정입니다.

 

모듈로 역원  c 언어 구현

int mul_inv(int a, int m) {
    int d0 = a, d1 = m;  
    int x0 = 1, x1 = 0; 
    int q, tmp; 

    while (d1 > 1) { 
        q = d0 / d1;  

        tmp = d0 - q * d1; 
        d0 = d1;  
        d1 = tmp;  
        tmp = x0 - q * x1; 
        x0 = x1;  
        x1 = tmp; 
    }

    if (d1 == 1) {  // d1이 1이면 역원이 존재
        return (x1 > 0) ? x1 : (x1 + m);  // x1이 음수면 m을 더해 양수로 변환 (mod m 의 특성)
    } else {
        return 0;  // d1이 1이 아닌 경우, 역원이 없어서 0 리턴
    }
}