[C 언어] 유클리드 호제법 증명과 재귀함수 구현
유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요. 유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다. 여담으로 최소공배수는 (두 수의 곱/gcd)
thfist-1071.tistory.com
알고리즘, 자료구조 카테고리에 포함되어 있지만 유클리드 호제법(유클리드 알고리즘)을 증명했었다.
다시 간단하게 설명하자면
\[GCD(A, B) = GCD(B, r)\]
임을 보였다.
유클리드 호제법은 귀류법으로 증명했었는데
간단하게 수식만으로 보자
유클리드 알고리즘 증명
\[G=GCD(A, B)\]
\[A = aG, B = bG \;(a, b \;are \;coprime)\]
\[A = Bq + r \iff aG = bGq + r \iff r = (a-bq)G\]
\[if (a-bq), b \;are \;not \;coprime\]
\[a-bq = mp, b = np\]
\[a-npq = mp.\]
\[but \; a = (m+nq)+, b = np \therefore (a-bq), b \;is \;coprime\]
\[\therefore GCD(A,B) = GCD(B, r)\]
확장된 유클리드 알고리즘
유클리드 알고리즘이 a, b의 최대공약수 GCD(a, b)를 구하는 알고리즘이었다면
확장 유클리드 알고리즘은 as + bt = GCD(a, b)를 만족하게 하는 정수 s, t를 구하는 알고리즘이다.
먼저 사용해보는게 이해가 수월하니
먼저 375, 275라는 숫자를 가지고 유클리드 호제법과 확장된 유클리드 호제법을 사용해보자.
유클리드 호제법은
\[375 = 275\times1 + 100\]
\[275 = 100\times2 + 75\]
\[100 = 75\times1 + 25\]
\[75 = 25\times3 + 0\]
\[25 = 0...\]
나누는 수가 0이면 a를 반환하므로 gcd(375, 275) = 25이다.
확장된 유클리드 알고리즘은 표를 그려 사용해보자.
a, b 대신 r1, r2를 사용하고
증명 시에는 r0, r1, r2, r3, r4, r5 이렇게 사용할 것이다. (ex. r0 = r1*q1 + r2로 사용할 것임)
| q | r1 | r2 | r | s1 | s2 | s | t1 | t2 | t |
| 375 | 275 | 1 | 0 | 0 | 1 | ||||
처음에 r1, r2는 알고 있었고
s1, s2는 1 0
t1 t2는 0 1로 초기값을 둔다.
이제 게산을 하면서 채워나갈 것이다.
$q = r_1/r_2$
$r = r_1 - q\times r_2$
$s = s_1 - q\times s_2$
$t = t_1 - q\times t_2$
이렇게 계산한다.
q는 몫이고 r은 나머지이고..
s랑 t는 각각 q랑 ?2 계산해서 ?1에서 빼면 되니까 쉽다.
처음 칸을 채워보자.
| q | r1 | r2 | r | s1 | s2 | s | t1 | t2 | t |
| 1 | 375 | 275 | 100 | 1 | 0 | 1 | 0 | 1 | -1 |
두 번째 칸의 초기값은 유클리드 호제법과 같다.
r2가 r1으로 가고 r은 r2로
s2-> s1, s - > s2
t2 -> t1, t->t2
이렇게 채워넣고 다시 계산해본다.
| q | r1 | r2 | r | s1 | s2 | s | t1 | t2 | t |
| 1 | 375 | 275 | 100 | 1 | 0 | 1 | 0 | 1 | -1 |
| 2 | 275 | 100 | 75 | 0 | 1 | -2 | 1 | -1 | 3 |
이 과정을 반복한다.
| q | r1 | r2 | r | s1 | s2 | s | t1 | t2 | t |
| 1 | 375 | 275 | 100 | 1 | 0 | 1 | 0 | 1 | -1 |
| 2 | 275 | 100 | 75 | 0 | 1 | -2 | 1 | -1 | 3 |
| 1 | 100 | 75 | 25 | 1 | -2 | 3 | -1 | 3 | -4 |
| 3 | 75 | 25 | 0 | -2 | 3 | -11 | 3 | -4 | 15 |
| 25 | 0 | 3 | -11 | -4 | 15 |
그리고 r2가 0이 되는 시점에 첨자가 1인 숫자들을 본다.
$as + bt = \gcd(a,b)$에서 gcd와 s, t를 구했다.
375*3 + 275*(-4) = 25
엄청엄청 신기하다..
이제 왜 그런지 살펴보자.
확장된 유클리드 알고리즘 증명
확장된 유클리드 알고리즘은 베주 항등식에서 비롯된다. 베주 항등식은 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼수 있다는 정리인데. 한 번 찾아보고 싶으면 찾아봐도 좋겠다.
이제 아까 말했듯이..
r0, r1, r2, r3로 부를것이다.
s와 t를 1, 0 0, 1로 초기값을 지정해둔 이유가 있다.
초기 조건
\[r_0 = a, r_1 = b\]
\[s_0 = 1, s_1 = 0\]
\[t_0 = 0, t_1 = 1\]
이고
\[as_i + b_ti = r_i\]
가 $i=0,1$에서 성립한다. (Base)
$375 = 375\times1 + 275\times0$
$275 = 375\times0 + 275\times1$
확장된 유클리드 알고리즘을 증명한다는건.. $r_{i+1} = 0$일때 $as_i + bt_i = r_i$가 $as + bt = \gcd(a,b)$임을 증명하는 것이다. i>=0이고 3의 배수인듯
표를 계속해서 그려나갈 때 마지막 행 부분에서 gcd, s, t를 구할 수 있다는 것.
그래서 우리는 $r_{i} = as_{i} + bt_{i}$이 성립함을 보이면 된다.
유클리드 알고리즘에서 계산한 $r_{i+2} = r_i - r_{i+1}q_{i+1}$이다.
(375 = 275*1 + 100에서 375가 r0 275가 r1, 1이 q1, 100이 r2이다.)
그리고 그 결과로 $r_{i+1} = 0$일때 $r_i$는 $\gcd(a,b)$였다.
우리가 계산한 방법에서 r과 똑같이 $s_{i+2} = s_i - s_{i+1}q_{i+1}$,
$t_{i+2} = t_i - t_{i+1}q_{i+1}$로 구했다.
수학적 귀납법으로 $as_i + bt_i = r_i$가 $i>1$에서 참이라고 가정하자.
$i+1$의 경우
\[r_{i+1} = r_{i-1} - r_iq_i\]
\[= (as_{i-1} + bt_{i-1}) - (as_i +bt_i)q_i\]
\[= a(s_{i-1} - s_iq_i) + b(t_{i-1} - t_iq_i)\]
$(s_{i-1} - s_iq_i) = s_{i+1}$이므로
\[= as_{i+1} + bt_{i+1}\]
\[\therefore r_i = as_i + bt_i\]
유클리드 호제법에서 $r_{i+1} = 0$일때 $r_i = \gcd(a,b)$이므로
확장된 유클리드 호제법에서는 $r_{i+1} = 0$일때, $as_i + bt_i = \gcd(a,b)$이다.
def EEA(r1, r2, u1, u2, v1, v2) :
if r2 == 0:
print(f'gcd: {r1}\nu: {u1}\nv: {v1}')
return
q = r1//r2
r = r1%r2
u = u1 - q*u2
v = v1 - q*v2
return EEA(r2, r, u2, u, v2, v)
EEA(26513, 32321, 1, 0, 0, 1)간단한 python 코드.
cryptohack에서는 서로소인 두 소수를 가지고 확장된 유클리드 알고리즘을 사용하도록 했다.
이럴 경우에 gcd(p, q) = 1이 되는데 gcd가 1인 경우는 모듈러 연산에서의 곱셈의 역원을 구하는데 사용된다.
이건 다음에 자세히 알아보자. 나도 공부해야한다..
