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

학교에서 정보보호이론을 수강하고 있는데 유클리드 알고리즘이 나온다. 2000년도 더 된 알고리즘이지만 그 증명이나 절차가 나에겐 직관적으로 와닿지가 않아서 몇 번을 봐도 세부사항을 곧잘 까먹었다. (사실 무슨 알고리즘이든 며칠 지나면 디테일을 까먹게 되지만.. -.-) 이번 기회에 확실하게 배우고 넘어갔지만 확장 유클리드 알고리즘은 한층 아리송해서 여기에 정리해본다. 유클리드 알고리즘은 잘 알고 있다고 가정한다.

유클리드 알고리즘은 다음과 같다.

두 양의 정수 ($a$), ($b$) 의 최대공약수 ($gcd(a,b)$)는 다음과 같은 절차를 거쳐 구할 수 있다.

$$r_0\leftarrow a,r_1\leftarrow b$$

$$r_{i+1}=r_{i-1}-q_i{r}_i,q_i=r_{i-1}/r_i$$

만약 ($r_{i+1}=0$) 이라면 ($r_i$) 가 바로 ($gcd(a,b)$) 이다.

그리고 확장 유클리드 알고리즘은 최대공약수 말고도 다음을 만족하는 두 개의 정수 ($s$), ($t$)를 추가로 구한다.

$$sa+tb=gcd(a,b)$$

의사코드로 쓰면 다음과 같다.

// 초기화

r1 ← a, r2 ← b

s1 ← 1, s2 ← 0

t1 ← 0, t2 ← 1

// 루프

while(r2 > 0){

　q ← r1 / r2

　r ← r1 - q*r2

　r1 ← r2

　r2 ← r

　s ← s1 - q*s2

　s1 ← s2

　s2 ← s

　t ← t1 - q*t2

　t1 ← t2

　t2 ← t

}

// 결과

gcd(a, b) ← r1

s ← s1

t ← t1

시험을 볼 때는 이걸 손으로 구해야 하기 때문에 외워야 하는데, 무작정 외우기엔 좀 길다. 다행히도 코드에 있는 규칙성을 주목하면 쉽게 외울 수 있다. 위 코드에서 유클리드 알고리즘만 떼놓고 보면 다음과 같다.

// 초기화

r1 ← a, r2 ← b

// 루프

while(r2 > 0){

　q ← r1 / r2

　r ← r1 - q*r2

　r1 ← r2

　r2 ← r

}

// 결과

gcd(a, b) ← r1

이건 그리 길지 않아서 확실히 외울 수 있다. 그리고 확장 유클리드 알고리즘에서 추가된 부분만 굵게 표시하면...

// 초기화

r1 ← a, r2 ← b

s1 ← 1, s2 ← 0

t1 ← 0, t2 ← 1

// 루프

while(r2 > 0){

　q ← r1 / r2

　r ← r1 - q*r2

　r1 ← r2

　r2 ← r

　s ← s1 - q*s2

　s1 ← s2

　s2 ← s

　t ← t1 - q*t2

　t1 ← t2

　t2 ← t

}

// 결과

gcd(a, b) ← r1

s ← s1

t ← t1

1. 초기값은 쉽게 외울 수 있다. 다음의 표를 머리 속에 넣어두자.

r1	r2	s1	s2	t1	t2
a	b	1	0	0	1

2. 루프 안에서는 기존의 (r, r1, r2)를 (s, s1, s2) 그리고 (t, t1, t2)로 그대로 치환하기만 하면 된다.

3. 결과값은 최대공약수가 r1이듯이 s, t도 s1, t1를 대입한다.

외우는 건 외우는 거고 그 증명은 어떻게 될까? 찾아보니 너무 짧아서 상당히 놀랐는데 수학적 귀납법을 이용해서 두 줄로 증명할 수 있다.

$$a{s}_i+b{t}_i=r_{i}fori=0,1$$

초기값들을 넣어서 확인해볼 수 있다. 이제 ($i>1$)일 때 참이라고 가정하고 수학적 귀납법을 써보자.

$$r_{i+1}=r_{i-1}-r_i{q}_i=(a{s}_{i-1}+b{t}_{i-1})-(a{s}_i+b{t}_i)q_i=a(s_{i-1}-s_i{q}_i)+b(t_{i-1}-t_i{q}_i)=a{s}_{i+1}+b{t}_{i+1}$$

따라서 ($r_{i+1}=0$) 일 때 ($a{s}_i+b{t}_i=r_i$) 는 ($as+bt=gcd(a,b)$) 가 된다. 증명 끝.