유클리드 알고리즘

유클리드 알고리즘(Euclidean Algorithm, 幾何算法)은 두 개의 자연수 또는 정수의 최대공약수(Greatest Common Divisor, GCD)를 효율적으로 구하기 위한 고전적인 알고리즘이다.

1 개요

유클리드 알고리즘은 고대 그리스의 수학자 유클리드(Euclid)가 그의 저서 『원론(Elements)』에서 소개한 방법으로, 두 수를 서로 나누는 과정을 반복하여 최대공약수를 구하는 방식이다. 이 알고리즘은 단순하면서도 계산 효율성이 높아 현대 수학, 컴퓨터 과학, 암호학 등 다양한 분야에서 널리 사용되고 있다.

2 알고리즘 절차

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

1. 두 수 a와 b(a > b)에 대해 a를 b로 나눈 나머지 r을 구한다.
2. r이 0이면 b가 최대공약수이다.
3. r이 0이 아니면 a를 b로, b를 r로 교체한 뒤 1단계로 돌아간다.

3 예시

1071과 462의 최대공약수를 구하는 과정은 다음과 같다.

1. 1071 ÷ 462 = 2 (나머지 147)
   • a = 1071, b = 462, r = 147
2. 462 ÷ 147 = 3 (나머지 21)
   • a = 462, b = 147, r = 21
3. 147 ÷ 21 = 7 (나머지 0)

따라서 최대공약수는 21이다.

4 확장 유클리드 알고리즘

확장 유클리드 알고리즘(Extended Euclidean Algorithm)은 최대공약수뿐만 아니라, 정수 계수 x와 y를 찾아 ax + by = gcd(a, b)를 만족하는 해를 구하는 방법이다. 이 알고리즘은 모듈로 연산에서 역원을 구하거나 디오판틴 방정식을 푸는 데 활용된다.

5 특성

• 알고리즘이 단순하고 계산량이 적어 매우 빠르다.
• 나머지가 절반 이하로 감소하기 때문에 반복 횟수가 로그에 비례한다.
• 소수나 큰 정수의 계산에서도 안정적으로 작동한다.

6 활용

• RSA 암호 알고리즘 등 공개키 암호 시스템
• 수론 관련 문제 해결
• 컴퓨터 프로그래밍에서 분수의 기약 형태 구하기
• 알고리즘 문제 해결에서 공약수 및 공배수 계산

7 같이 보기

• 최대공약수
• 확장 유클리드 알고리즘
• RSA 암호 알고리즘
• 소수
• 디오판틴 방정식

8 참고 문헌

• Euclid. *Elements*. circa 300 BCE.
• Knuth, Donald E. *The Art of Computer Programming, Volume 2: Seminumerical Algorithms*. Addison-Wesley, 1997.