Graphics Programming
확장 유클리드 알고리즘(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를 대입한다.
외우는 건 외우는 거고 그 증명은 어떻게 될까? 찾아보니 너무 짧아서 상당히 놀랐는데 수학적 귀납법을 이용해서 두 줄로 증명할 수 있다.
$$ 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) $) 가 된다. 증명 끝.
