정수론 (7) - 확장 유클리드 알고리즘

RSA 암호 얘기로 넘어가기 전에 한 가지 더 알아야 할 것이 있습니다. 바로 확장 유클리드 알고리즘입니다.

 

확장 유클리드 알고리즘

정수론 (2) - 베주 항등식 에서 베주 항등식에 대해서 알아봤습니다. 베주 항등식의 내용은 다음과 같았습니다.

 

$a, b$에 대하여 $ax + by = \text{gcd}(a, b)$를 만족하는 정수 $x, y$가 존재한다.

 

그런데 베주 항등식은 이러한 $x, y$의 존재성에 대해서만 얘기하고 실제로 $x, y$를 어떻게 구하는지에 대해서는 언급하지 않습니다. 하지만 확장 유클리드 알고리즘을 활용하면 구할 수 있습니다. 사실 확장 유클리드 알고리즘은 유클리드 알고리즘을 거꾸로 하면 됩니다. 단계는 아래와 같습니다.

 

1. 먼저 유클리드 호제법을 통해 $a, b$의 최대공약수를 구합니다.
2. 유클리드 호제법의 식들을 위에서부터 1번, 2번, 3번, ..., $n$번 식이라고 했을 때, 먼저 $n-1$번 식을 나머지에 대해 이항합니다.
3. $n-2$번 식을 나머지에 대해 이항한 뒤, $n-1$번 식에 대입합니다.
4. $n-3$번 식을 나머지에 대해 이항한 뒤, $n-1$번 식에 대입합니다.
5. 이 과정을 $\text{gcd}(a, b) = ax + by$ 의 꼴로 표현될 때까지 반복합니다.

 

일례로 102와 38의 최대공약수를 유클리드 알고리즘으로 구해보면,
$$
\begin{align}
102 &= 2 \times 38 + 26 \\
38 &= 1 \times 26 + 12 \\
26 &= 2 \times 12 + 2 \\
12 &= 6 \times 2 + 0.
\end{align}
$$
따라서 최대공약수는 나머지가 0이 되기 직전의 나머지인 2입니다. 그럼 이제부터 확장 유클리드 알고리즘으로 $102x + 38y = 2$ 가 되도록 하는 $x, y$를 구해보겠습니다. 먼저 마지막에서 두 번째 식을 다음과 같이 나머지인 $2$에 대해 정리합니다.
$$
2 = 26 - 2 \times 12
$$
그 위의 식도 마찬가지로 나머지인 $12$에 대해 이항합니다.
$$
12 = 38 - 1 \times 26
$$
이 식을 $2 = 26 - 2 \times 12$에 대입합니다.
$$
\begin{align}
2 &= 26 - 2 \times (38 - 1 \times 26) \\
&= 3 \times 26 - 2 \times 38
\end{align}
$$
이제 이 과정을 반복하면 됩니다. 그 위의 식도 나머지인 $26$에 대해 이항한 뒤,
$$
26 = 102 - 2 \times 38
$$
이 식을 $2 = 3 \times 26 - 2 \times 38$에 대입합니다.
$$
\begin{align}
2 &= 3 \times 26 - 2 \times 38 \\
&= 3 \times (102 - 2 \times 38)-2 \times 38 \\
&= 3 \times 102 - 8 \times 38
\end{align}
$$
따라서 $x = 3, y = -8$ 입니다.

 

이게 확장 유클리드 알고리즘 내용의 끝입니다! 나쁘지 않죠? 다음 번에는 오일러 공식과 확장 유클리드 알고리즘을 활용하여 RSA 암호에 대해 알아보겠습니다.