🔒유클리드 알고리즘(유클리드 호제법)

RSA 암호 시스템을 이해하기 위해 필요한 수학적 이론인 유클리드 호제법에 대해 알아볼 것이다.
이야기 하기에 앞서 유클리드 호제법에 사용되는 수학기호와 용어에 대한 설명은 다음과 같다.

수학기호 및 용어

$a\, |\, b$ : 정수 $b$는 정수 $a$로 나누어 떨어진다.
$\in$ : (왼쪽이 오른쪽의) 원소이다.
$\exist$ : 존재한다. (exist)
$\mathbb{Z}$ : 정수 집합

---

약수의 정의

$a,b\in\mathbb{Z}\; (a\ne0)$
$a$가 $b$의 약수라는 말은 $b=ak,\, \exist k \in \mathbb{Z}$ 라는 말과 동치이다.

0의 약수

$x\,|\,0\; \Rightarrow\; x$는 모든 정수
0의 약수는 모든 정수 (모든 정수는 0의 배수)$\Rightarrow\,x\,|\,0\;\Rightarrow\,0=x\times k\, (k는\, 0)\, ,\,\exist k\in\,\mathbb{Z}$

공약수(최대 공약수)

$\gcd(a,b)$ 라고 나타낼 수 있으며 $\gcd$는 greatest common diviser (최대 공약수)의 약자이다.
${\sf ex})\gcd(12,3)=3\\\quad\;\,\gcd(32,18)=2$

---

유클리드 알고리즘(유클리드 호제법)

$\gcd(A,B)=\gcd(B,r)$

각 문자의 크기를 비교해보면 $0\le r<B<A$ 라고 나타낼 수 있는데 유클리드 호제법을 보면 $A$보다 작은 $B,r$의 최대공약수가 $A,B$의 최대공약수와 같다고 나와있다.
따라서 위의 식에서 = 의 의미는 같은 값 $\gcd$를 좀 더 작은 수로 축소해서 나타낸다는 말이 될 수 있다. 또한 이 말을 통해 $\gcd(B,r)$을 계속 축소할 수 있다는 것을 알 수 있다.

위의 $B$의 식은 $\gcd(B,r)$을 한번 더 축소했다고 가정했을 때의 식이다. 이때 $q,q_1$은 몫을 나타내고 $r,r_1$은 나머지를 나타낸다.

증명

$\gcd(A,B)=\gcd(B,r)$
$($단, $A>B,\,A\ne B,\,A=qB+r,\,0\le r<B)$

${\sf pf}\;\gcd(A,B)=g\Rightarrow \gcd(B,r)=g\\\quad\;$이때 $\gcd(B,r)=g$ 가 우리가 증명할 명제이다. 공통인수인 $g$를 사용하여 $A,B$를 식으로 나타내면$\quad \,A=ga\\\quad \,B=gb$ 와 같다. 단, $a,b$ 는 서로소이다.

---

서로소란?

: $a,b$가 서로소라는건, $\gcd(a,b)=1\Leftrightarrow$ 공통인수가 없다.(1을 제외하고)

$a,b$가 서로소가 아닐 경우

$\gcd(a,b)\ne1\,,\,\gcd(a,b)=m\Rightarrow m\,|\,a\,,\,m\,|\,b$
$A=ga\, ,\,B=gb$ 를 $gm$으로 나눌 수 있고 모두 약분된다. 그럼 $A,B$의 공통인수는 $gm$이 된다.
따라서 $\gcd(A,B)=g\Rightarrow$ 모순
이를 정리하자면
$\gcd(A,B)=g\\A=ga\,,\,B=gb\;\,$ $($단, $\gcd(a,b)=1)$

---

다시 증명을 이어서 하면
${\sf pf}\;A=qB+r$ 은 $ga=qgb+r$ 과 같이 나타낼 수 있고
$\quad \;r=ga-qgb=g(a-qb)=gr^\prime$ 을 통해 $g\,|\,r$ 이 가능하다.
$\quad B=gb\,,r=gr^\prime\,\Rightarrow\,g\,|\,b\,,\,g\,|\,r$
$\quad$위 식을 통해 $g$가 $B,r$의 공약수임을 알 수 있지만 최대공약수인지는 알 수 없다.
$\quad$따라서 $\gcd=(B,r^\prime)=1$임을 보여야한다.

$\quad$우리는 귀류법을 사용할 것인데 $\gcd(b,r^\prime)=\alpha\;\,(a\ne1)$ 라고 가정하고 식을 써보면 다음과 같다.
$\quad A=qB+r\Rightarrow ga=qgb+gr^\prime$
$\quad b=\alpha b^\prime$
$\quad r^\prime=\alpha r^{\prime\prime}$
$\quad$이때 $\gcd(b^\prime,r^{\prime\prime})=1$ 이며 위 $b\,,\,r^\prime$ 에 대한 두 식을 $ga=qgb+gr^\prime$ 에 대입한다.
$\quad A=ga=qg\alpha b^\prime+g\alpha r^{\prime\prime}=ga(qb^\prime+r^{\prime\prime})\\\quad\Rightarrow g\alpha\,|\,A\\ \quad\quad\;g\alpha\,|\,B=gb=g\alpha b^\prime$
$\quad$위 식은 $\gcd(A,B)=\gcd(B,r)$ 에 모순이다.
$\quad$즉, 최대공약수가 $g\alpha$ 이기 때문에 $A\,,\,B$의 최대공약수가 $g$라는 것에 모순이다.

$\quad$위 귀류법을 통해 $\gcd(b,r^\prime)=1$ 이 증명된다.
$\quad$그럼 $\gcd(B,r)=g$ 또한 증명이 되고 따라서 $\gcd(A,B),\gcd(B,r)$의 값이 g로 같다.
$\quad$결론적으로, $\gcd(A,B)=\gcd(B,r)$ 이라는 것을 알 수 있다.

---

예제

${\sf ex})\,\gcd(12345,123)=\gcd(123,45)\\\quad\quad\quad\quad\quad\quad\quad\quad\;\;\,=\gcd(45,33)\\\quad\quad\quad\quad\quad\quad\quad\quad\;\;\, =\gcd(33,12)\\\quad\quad\quad\quad\quad\quad\quad\quad\;\;\, =\gcd(12,9)\\\quad\quad\quad\quad\quad\quad\quad\quad\;\;\, =\gcd(9,3)\\\quad\quad\quad\quad\quad\quad\quad\quad\;\;\, =\gcd(3,0) =3$

틀린부분이나 이상한 부분 있으면 알려주세요...!