Graphics Programming

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

Season 1/수학

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

minseoklee 2015. 4. 18. 01:33

학교에서 정보보호이론을 수강하고 있는데 유클리드 알고리즘이 나온다. 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를 대입한다.


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


$$ as_i + bt_i = r_i ~~~for~ i = 0, 1 $$


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


$$ r_{i+1} = r_{i-1} - r_i q_i = (as_{i-1} + bt_{i-1}) - (as_i + bt_i)q_i = a(s_{i-1} - s_i q_i) + b(t_{i-1} - t_i q_i) = as_{i+1} + bt_{i+1} $$


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


Comments