확장 유클리드 알고리즘 계산기

확장 유클리드 알고리즘 계산기는 두 정수의 최대공약수(GCD)를 계산하고, gcd(a, b) = s·a + t·b를 만족하는 정수 s와 t인 베주 계수(Bézout coefficients)를 찾습니다. 최대공약수 계산뿐만 아니라, 이 도구는 전체 애니메이션이 포함된 단계별 나눗셈 표, 역대입 과정, 모듈로 역수 계산을 제공하여 정수론 강의, 암호학 학습 및 알고리즘 문제 풀이에 이상적입니다.

확장 유클리드 알고리즘이란?

확장 유클리드 알고리즘(EEA)은 유클리드의 고전적인 GCD 알고리즘의 확장판입니다. 기본 알고리즘이 연속적인 나눗셈을 통해 gcd(a, b)를 찾는 동안, 확장 버전은 각 나머지가 원래 입력값들의 선형 결합으로 어떻게 표현되는지 기록하는 두 개의 정수 수열을 동시에 추적합니다.

알고리즘 작동 원리

EEA는 각 나눗셈 단계에서 세 쌍의 값 — (r, s, t) —을 유지합니다:

1. 초기화: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. 각 단계: 몫 q = ⌊rₙ₋₁ / rₙ⌋를 계산한 후, rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ으로 업데이트
3. 나머지가 0이 되면 중단하며, 이때 직전의 나머지가 gcd(a, b)입니다.
4. 해당하는 s와 t 값이 베주 계수가 됩니다.

단계별 예시: gcd(252, 105)

결과: gcd(252, 105) = 21이며, 베주 항등식은 다음과 같습니다: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). 위 계산기에서 직접 입력하여 정확한 계수를 확인해 보세요.

확장 유클리드 알고리즘의 응용

1. 모듈로 역수 (암호학)

가장 중요한 응용 분야는 모듈로 역수를 계산하는 것입니다. gcd(a, m) = 1인 경우, 베주 계수 s는 다음을 만족합니다:

모듈로 역수는 RSA 암호화(개인 키 지수 d 계산), 디피-헬먼(Diffie-Hellman) 키 교환, 타원 곡선 암호학 등에 필수적입니다.

2. 일차 디오판토스 방정식 풀이

방정식 ax + by = c는 gcd(a, b)가 c의 약수일 때만 정수해를 가집니다. 이 경우, d = gcd(a, b)이고 s, t가 베주 계수일 때 특수해는 x₀ = s·(c/d), y₀ = t·(c/d)가 됩니다.

3. 중국인의 나머지 정리

EEA는 각 모듈로의 역수를 계산함으로써 중국인의 나머지 정리(x ≡ a₁ (mod m₁) 및 x ≡ a₂ (mod m₂)를 만족하는 x 찾기)의 구성적 증명과 계산에 사용됩니다.

4. 분수 약분 및 최소공배수

gcd(a, b) = 1은 분수 a/b가 이미 기약분수임을 확인해 줍니다. 최소공배수는 lcm(a, b) = |a·b| / gcd(a, b)로 구할 수 있습니다.

베주 계수는 유일하지 않습니다

베주 계수 s와 t는 유일하지 않습니다. (s, t)가 하나의 해라면, 임의의 정수 k에 대해 (s + k·(b/d), t − k·(a/d)) 또한 해가 됩니다 (단, d = gcd(a, b)). EEA는 |s| ≤ |b/d| 및 |t| ≤ |a/d|를 만족하는 해를 반환합니다.

시간 복잡도

확장 유클리드 알고리즘은 기본 유클리드 알고리즘과 마찬가지로 O(log min(a, b)) 번의 반복으로 실행됩니다. 라메의 정리(Lamé's theorem)에 따르면, 단계 수는 더 작은 입력값의 십진수 자릿수의 5배를 절대 넘지 않습니다. 덕분에 암호학에서 사용되는 매우 큰 정수에 대해서도 매우 효율적입니다.

자주 묻는 질문

확장 유클리드 알고리즘이란 무엇인가요?

확장 유클리드 알고리즘은 유클리드의 GCD 알고리즘을 확장하여 gcd(a, b) = s·a + t·b를 만족하는 베주 계수 s와 t를 함께 계산하는 방식입니다. 나눗셈 과정 전체에서 각 나머지가 a와 b의 선형 결합으로 어떻게 표현되는지 추적합니다.

베주 계수란 무엇인가요?

베주 계수는 정수론의 베주 항등식에 의해 존재가 보장되는 정수 s와 t를 말합니다. 이들은 gcd(a, b) = s·a + t·b를 만족하며, 확장 유클리드 알고리즘을 통해 효율적으로 계산됩니다. 모듈로 역수 계산, 디오판토스 방정식 풀이, 중국인의 나머지 정리 등에 사용됩니다.

확장 유클리드 알고리즘으로 모듈로 역수를 어떻게 찾나요?

gcd(a, b) = 1(a와 b가 서로소)인 경우, 베주 계수 s는 s·a ≡ 1 (mod b)를 만족합니다. a mod b의 모듈로 역수는 s mod b(양수가 되도록 조정됨)입니다. 이 계산기는 결과 창에 이를 직접 표시합니다.

모듈로 역수가 존재하지 않는 경우는 언제인가요?

a modulo m의 모듈로 역수는 오직 gcd(a, m) = 1일 때만 존재합니다. 만약 gcd(a, m) > 1이라면, a·x ≡ 1 (mod m)을 만족하는 정수 x는 존재하지 않습니다.

확장 유클리드 알고리즘의 시간 복잡도는 어떻게 되나요?

기본 유클리드 알고리즘과 동일한 O(log min(a, b))번의 나눗셈이 필요합니다. 라메의 정리에 따라 단계 수는 작은 입력값 자릿수의 5배 이내로 제한되므로 매우 효율적입니다.

추가 리소스

• 베주 항등식 - 위키백과