알고리즘 원리:
확장 유클리드 알고리즘은 두 정수 a와 m의 최대공약수 gcd(a, m)를 계산할 뿐만 아니라, 다음을 만족하는 정수 x와 y도 찾습니다: ax + my = gcd(a, m)。
이는 베주 항등식(Bézout's identity)의 응용입니다.
알고리즘 단계:
- 유클리드 알고리즘:나눗셈 알고리즘을 사용하여 gcd(a, m)를 계산하고 각 단계의 몫과 나머지를 기록합니다.
- 역대입:마지막 단계부터 시작하여 역으로 대입하며 각 나머지를 a와 m의 선형 결합으로 표현합니다.
- 계수 구하기:최종적으로 ax + my = gcd(a, m)를 만족하는 계수 x와 y를 얻습니다.
모듈러 역원:
gcd(a, m) = 1일 때(즉, a와 m이 서로소), a의 모듈러 m에 대한 곱셈 역원이 존재하며 a-1 mod m으로 표시합니다. 이 경우 x가 모듈러 역원이며, 다음을 만족합니다: a × x ≡ 1 (mod m)。
x가 음수인 경우 양수로 조정해야 합니다: x' = x mod m.
응용 분야:
- 암호학:RSA 알고리즘에서 개인 키를 계산하려면 모듈러 역원을 찾아야 합니다.
- 정수론 문제:ax ≡ b (mod m) 형태의 선형 합동식 풀이.
- 조합론:모듈러 조합 계산 (뤼카 정리 등)
- 경쟁 프로그래밍:나눗셈의 정밀도 문제를 피하기 위한 빠른 모듈러 역원 계산
시간 복잡도:
O(log min(a, m)), 유클리드 알고리즘과 동일