확장 유클리드 알고리즘

확장 유클리드 알고리즘(Extended Euclidean Algorithm, 拡張幾何算法)은 두 개의 정수 a, b에 대해 최대공약수(Greatest Common Divisor, GCD)와 함께 정수 계수 x, y를 찾아 ax + by = gcd(a, b)를 만족하는 해를 구하는 알고리즘이다.

1 개요

확장 유클리드 알고리즘은 기본 유클리드 알고리즘을 변형하여, 최대공약수를 구하는 과정 중 각 단계에서 선형 결합의 계수를 추적함으로써 최종적으로 해당 방정식의 해를 얻는 방법이다. 이 알고리즘은 모듈로 연산에서의 역원 계산, 디오판틴 방정식 풀이, RSA 암호 시스템 등 다양한 수학 및 컴퓨터 과학 분야에서 중요한 역할을 한다.

2 알고리즘 절차

확장 유클리드 알고리즘은 다음과 같은 과정을 따른다.

1. 두 정수 a, b에 대해, b가 0이면 (gcd, x, y) = (a, 1, 0)을 반환한다.
2. 그렇지 않으면, (gcd, x1, y1) = 확장유클리드(b, a mod b)를 재귀적으로 호출한다.
3. x = y1
4. y = x1 - (a ÷ b) × y1
5. (gcd, x, y)를 반환한다.

3 예시

99와 78에 대해 확장 유클리드 알고리즘을 적용하는 과정은 다음과 같다.

1. 99 ÷ 78 = 1 (나머지 21)
2. 78 ÷ 21 = 3 (나머지 15)
3. 21 ÷ 15 = 1 (나머지 6)
4. 15 ÷ 6 = 2 (나머지 3)
5. 6 ÷ 3 = 2 (나머지 0)

따라서 gcd(99, 78) = 3이다.

거꾸로 역추적하여 계수를 구한다.

1. 3 = 6 - 2×3
2. 3 = (15 - 2×6) - 2×(6 - 2×3) = 5×15 - 2×21
3. 3 = (78 - 3×21)×5 - 2×21 = 5×78 - 17×21
4. 3 = 5×78 - 17×(99 - 78) = 22×78 - 17×99

즉, 99×(-17) + 78×22 = 3이다.

4 활용

• 모듈로 연산에서 역원(modular inverse) 계산
• 선형 디오판틴 방정식의 해 구하기
• RSA 암호 알고리즘의 키 생성 과정
• 큰 수 계산이나 암호 시스템에서 효율적이고 필수적인 연산 처리

5 특성

• 유클리드 알고리즘과 유사한 시간 복잡도(O(log min(a, b)))를 가진다.
• 재귀적 혹은 반복적으로 구현할 수 있으며, 메모리 사용량이 적다.
• 최대공약수 외에 선형 결합 계수를 함께 제공한다는 점이 큰 장점이다.

6 같이 보기

• 유클리드 알고리즘
• 최대공약수
• 모듈로 연산
• RSA 암호 알고리즘
• 디오판틴 방정식

7 참고 문헌

• Cormen, Thomas H., et al. *Introduction to Algorithms*. MIT Press, 2009.
• Rosen, Kenneth H. *Elementary Number Theory and Its Applications*. Pearson, 2010.