[이산수학] Euclidean Algorithm, Extended Euclid algorithm (확장 유클리드 알고리즘)

r0, r1 두 수의 최대공약수를 구하는 방법

 

작은 수에서는 쉽다. 두 수를 소인수분해해서 공통 소인수를 찾고 그걸 곱해준다.

 

하지만 큰 수에 대해서는 복잡해진다. 어떻게 쉽게 계산할 수 있을까?

 

 

$gcd(r_0, r_1) = gcd(r_0 - r_1, r_1)$

• 핵심 아이디어
  • 큰 수의 gcd를 구하는 문제를 점점 더 작은 수의 gcd를 구하는 문제로 바꾼다.
  • 이 과정을 재귀적으로 반복한다.
  • 마지막에 $gcd(r_1, 0)$ 이 나올 때 $r_1$이 원래 gcd이다.
• 긴 숫자일수록 복잡도는 입력 비트 수에 선형적으로 증가한다.

증명

1. a와 b의 최대공약수 d가 있다. d는 a와 b 모두를 나눌 수 있다.

2. a는 $a = kb + r$이라는 식으로 표현 가능하다. 여기서 k는 a를 b로 나눈 몫, r은 a를 b로 나눈 나머지이다.

3. 이것은 $ a \ mod  \ b = a - kb $ 로 변형할 수 있다. (r에 대해 정리)

4. d는 b를 나눌 수 있기 때문에 kb 또한 나눌 수 있다. 그리고 a도 나눌 수 있어 a - kb 도 d로 나눌 수 있다. 그러므로 d | (a mod b)

5. 우리는 이미 d가 b를 나눈다는 사실을 알고 때문에 gcd 정의를 통해 d = gcd (b, a mod b) 를 얻을 수 있다.

 

이를 코드로 표현하면 다음과 같다.

 

A = a, B = b
while B > 0
	R = A mod B
    A = B, B = R
return A // B가 0이 될때 A가 최대 공약수가 된다.

 

재귀 알고리즘으로도 표현 가능하다

 

Euclid(a, b)
	if b = 0 return a
    else return Euclid(b, a mod b)

 

• ex) Euclid(76, 16)
  • 76 = 4 X 16 + 12 = Euclid(16, 12)
  • 16 = 1 X 12 + 4 = Euclid(12, 4)
  • 12 = 3 X 4 + 0 = Euclid(4, 0)
  • 4가 gcd(76, 16)이 된다.

 

Extended Euclidean Algorithm (확장 유클리드 알고리즘) 

모듈러 역수를 구하기 위해 사용할 수 있다. $b^{-1} mod m$

 

$gcd (r_0, r_1) = s \cdot r_0 + t \cdot r_1 = 1$ 이 수식에 mod $r_0$을 한다.

$ s \cdot 0 + t \cdot r_1 \equiv 1 \ mod \ r_0 $

$ t \cdot r_1 \equiv 1 \ mod \ r_0 $

 

$r_1$ 을 $r_0$으로 나눈 나머지가 1이 되는 t가 있다면 t가 $r_1$의 역원이 된다.

 

gcd($r_0$, $r_1$) = 1 이여야 $r_1$의 모듈러 역원이 존재한다.

-> s와 t를 조정하여 $s \cdot r_0 + t \cdot r_1 \rightarrow 1$ 이 되도록 한다.

 

확장 유클리드 알고리즘의 코드는 다음과 같다.

 

int extendedEuclid(int m, int b)
{
	int a1 = 1, a2 = 0, a3 = m;
	int b1 = 0, b2 = 1, b3 = b;
	while (1)
	{
		if (b3 == 0) // 역원이 존재하지 않는다.
		{
			return 0;
		}
		if (b3 == 1) // 역원이 b2가 역원이 된다.
		{
			return b2;
		}
		int q = a3 / b3; // 몫을 구함
		int t1 = a1 - q * b1;
		int t2 = a2 - q * b2;
		int t3 = a3 - q * b3; // 나머지를 구함
		a1 = b1;
		a2 = b2;
		a3 = b3;
		b1 = t1;
		b2 = t2;
		b3 = t3;
	}
}

 

• ex) m = 11, b = 3을 넣었을 때

a1 : 1 a2 : 0 a3 : 11
b1 : 0 b2 : 1 b3 : 3
a1 : 0 a2 : 1 a3 : 3
b1 : 1 b2 : -3 b3 : 2 // a1 - q * b1, a2 - q * b2, a3 - q * b3, 
a1 : 1 a2 : -3 a3 : 2 // 값 업데이트
b1 : -1 b2 : 4 b3 : 1 // // a1 - q * b1, a2 - q * b2, a3 - q * b3, 
4 // b3 = 1일 때 b2가 모듈러 역수

 

b의 모듈러 역수는 4가 된다.

 

표 예시

모듈러 역수가 존재하지 않는다.

31이 18의 모듈러 역수

-470에 1023을 더한 553이 37의 모듈러 역수