유클리드 알고리즘 편집하기

유클리드 알고리즘(Euclidean Algorithm, 幾何算法)은 두 개의 자연수 또는 정수의 최대공약수(Greatest Common Divisor, GCD)를 효율적으로 구하기 위한 고전적인 알고리즘이다.
==개요==
유클리드 알고리즘은 고대 그리스의 수학자 유클리드(Euclid)가 그의 저서 『원론(Elements)』에서 소개한 방법으로, 두 수를 서로 나누는 과정을 반복하여 최대공약수를 구하는 방식이다. 이 알고리즘은 단순하면서도 계산 효율성이 높아 현대 수학, 컴퓨터 과학, 암호학 등 다양한 분야에서 널리 사용되고 있다.
==알고리즘 절차==
유클리드 알고리즘은 다음과 같은 과정을 따른다.
#두 수 a와 b(a > b)에 대해 a를 b로 나눈 나머지 r을 구한다.
#r이 0이면 b가 최대공약수이다.
#r이 0이 아니면 a를 b로, b를 r로 교체한 뒤 1단계로 돌아간다.
==예시==
1071과 462의 최대공약수를 구하는 과정은 다음과 같다.
#1071 ÷ 462 = 2 (나머지 147)
#*a = 1071, b = 462, r = 147
#462 ÷ 147 = 3 (나머지 21)
#*a = 462, b = 147, r = 21
#147 ÷ 21 = 7 (나머지 0)
따라서 최대공약수는 21이다.
==[[확장 유클리드 알고리즘]]==
확장 유클리드 알고리즘(Extended Euclidean Algorithm)은 최대공약수뿐만 아니라, 정수 계수 x와 y를 찾아 ax + by = gcd(a, b)를 만족하는 해를 구하는 방법이다. 이 알고리즘은 모듈로 연산에서 역원을 구하거나 디오판틴 방정식을 푸는 데 활용된다.
==특성==
*알고리즘이 단순하고 계산량이 적어 매우 빠르다.
*나머지가 절반 이하로 감소하기 때문에 반복 횟수가 로그에 비례한다.
*소수나 큰 정수의 계산에서도 안정적으로 작동한다.
==활용==
*RSA 암호 알고리즘 등 공개키 암호 시스템
*수론 관련 문제 해결
*컴퓨터 프로그래밍에서 분수의 기약 형태 구하기
*알고리즘 문제 해결에서 공약수 및 공배수 계산
==같이 보기==
*[[최대공약수]]
*[[확장 유클리드 알고리즘]]
*[[RSA 암호 알고리즘]]
*[[소수]]
*[[디오판틴 방정식]]
==참고 문헌==
*Euclid. *Elements*. circa 300 BCE.
*Knuth, Donald E. *The Art of Computer Programming, Volume 2: Seminumerical Algorithms*. Addison-Wesley, 1997.
==각주==
[[분류:수학]]
[[분류:알고리즘]]