유클리드 호제법 (Euclidean Algorithm)
유클리드 호제법은 두 양의 정수 $a$와 $b$의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘입니다. 기원전 300년경 유클리드의 저서 《원론(Elements)》에 기록된, 인류가 사용한 최초의 알고리즘 중 하나입니다.
1. 기본 원리
두 정수 $a$와 $b$의 최대공약수를 $\text{gcd}(a, b)$라고 할 때, 다음 원리가 성립합니다.
원리: 큰 정수 $a$를 작은 정수 $b$로 나눈 나머지 $r$가 있다면, $a$와 $b$의 최대공약수는 $b$와 $r$의 최대공약수와 항상 같다는 원리입니다. $$\text{gcd}(a, b) = \text{gcd}(b, r)$$
이 원리를 이용하여 나머지가 $0$이 될 때까지 계속해서 나누는 과정을 반복하며, 나머지가 $0$이 되기 직전의 나누는 수가 바로 최대공약수가 됩니다.
2. 유클리드 호제법 예시
두 정수 $a=1071$과 $b=462$의 최대공약수를 구해보겠습니다.
| 단계 | 계산식 ($a=bq+r$) | 나머지 $r$ |
|---|---|---|
| 1단계 | $1071 = 462 \times 2 + 147$ | $147$ |
| 2단계 | $\text{gcd}(462, 147)$ 계산을 위해 $462$를 $147$로 나눔 | |
| 3단계 | $462 = 147 \times 3 + 147 \times 3 + 21$ | $21$ |
| 4단계 | $\text{gcd}(147, 21)$ 계산을 위해 $147$을 $21$로 나눔 | |
| 5단계 | $147 = 21 \times 7 + 0$ | $0$ |
결과: 나머지가 $0$이 된 5단계에서 나누는 수는 $21$입니다.
$$\text{gcd}(1071, 462) = \mathbf{21}$$
3. 알고리즘의 중요성
- 효율성: 반복되는 나눗셈 횟수가 적어 매우 빠르게 최대공약수를 찾을 수 있습니다.
- 확장 유클리드 호제법: 이 기본 원리를 확장하여 베주 항등식 $ax + by = \text{gcd}(a, b)$을 만족하는 정수 $x$와 $y$를 찾는 데 사용됩니다.
- 암호학: RSA 암호화의 개인 키 $d$를 계산할 때, 이 확장된 유클리드 호제법이 필수적으로 사용됩니다.