모듈러 역원 계산기
확장 유클리드 알고리즘으로 ax ≡ 1 (mod m) 을 풀고, 중국인의 나머지 정리로 연립 합동식도 계산합니다. 호제법 과정과 역원이 없는 이유까지 보여줍니다.
3 × 4 = 12 ≡ 1이라 역원은 4입니다.
3x ≡ 1 (mod 11)
x = 4
확인: 3 × 4 = 12 ≡ 1 (mod 11)
유클리드 호제법
| 나눗셈 | 몫 | 나머지 |
|---|---|---|
| 3 = 0 × 11 + 3 | 0 | 3 |
| 11 = 3 × 3 + 2 | 3 | 2 |
| 3 = 1 × 2 + 1 | 1 | 1 |
| 2 = 2 × 1 + 0 | 2 | 0 |
나머지가 0이 되기 직전의 나머지가 gcd입니다. 확장 유클리드는 이 과정을 거꾸로 따라가며 gcd를 a와 m의 조합으로 나타내는 계수까지 함께 구합니다.
a로 나누는 대신 a·x ≡ 1을 만족하는 x를 곱합니다. 그 x는 gcd(a, m) = 1 일 때만 있습니다. 확장 유클리드로 a·x + m·y = gcd를 만족하는 계수를 구하면, gcd가 1 일 때 양변을 mod m으로 보아 m·y가 사라지고 a·x ≡ 1이 됩니다 — 그 x가 곧 역원입니다.
공개 지수 e의 역원을 φ(n) 에 대해 구한 것이 개인 지수 d입니다. 확장 유클리드는 자릿수에 비례하는 시간이면 끝나므로 역원은 순식간에 구할 수 있지만, 소인수분해로 φ(n) 을 알아내는 것은 어렵습니다 — 이 비대칭이 RSA를 떠받칩니다. 위 예의 “17 mod 3120”이 교과서에 나오는 그 계산입니다.
계산 방법
- 1모듈러 역원과 연립 합동식 중 무엇을 구할지 고릅니다.
- 2역원이라면 a와 법(mod m)을 넣습니다.
- 3연립 합동식이라면 나머지와 법을 세 쌍 넣습니다. 법들이 서로소여야 합니다.
- 4유클리드 호제법 과정과 확인 계산을 함께 봅니다.
자주 묻는 질문
a와 곱해서 1이 되는 수입니다. ax ≡ 1 (mod m) 을 만족하는 x이며, 나머지 세계에서 a로 나누는 것은 이 x를 곱하는 것과 같습니다. mod 11에서 3의 역원은 4입니다 — 3 × 4 = 12이고 12를 11로 나눈 나머지가 1 이기 때문입니다.
gcd(a, m) 이 1이 아니면 없습니다. mod 12에서 4의 역원은 없습니다 — 4에 무엇을 곱해도 12 와의 공약수 4가 남아 나머지가 4의 배수만 될 수 있고 1이 될 수 없기 때문입니다. 법이 소수면 0 말고는 모두 역원이 있습니다.
유클리드 호제법으로 gcd를 구하면서 gcd를 a·x + m·y로 나타내는 계수까지 함께 따라갑니다. gcd가 1이면 a·x + m·y = 1이고, 양변을 mod m으로 보면 m·y가 사라져 a·x ≡ 1이 됩니다. 그 x가 역원입니다.
법이 크면 못 하기 때문입니다. 확장 유클리드는 자릿수에 비례하는 시간이면 끝나지만, 하나씩 넣어 보는 것은 법의 크기에 비례합니다. 법이 수백 자리인 암호 계산에서는 차이가 결정적입니다.
여러 나머지 조건을 한꺼번에 만족하는 수를 찾는 방법입니다. 법들이 서로소이면 법들의 곱 안에서 해가 정확히 하나 있습니다. "3으로 나누면 2, 5로 나누면 3, 7로 나누면 2인 수"를 묻는 옛 문제가 이것이고, 답은 mod 105에서 23 하나입니다.
RSA에서 개인키를 만들 때 쓰는 계산이 모듈러 역원입니다. 공개 지수 e의 역원을 φ(n) 에 대해 구한 것이 개인 지수 d입니다. 역원은 순식간에 구할 수 있지만 소인수분해로 φ(n) 을 알아내는 것은 어렵다는 비대칭이 RSA를 떠받칩니다.
알아두면 좋은 점
- 자바스크립트 정수 범위 안에서만 계산합니다. 10¹⁵을 넘는 수는 다루지 않습니다.
- 연립 합동식은 법들이 서로소일 때만 풉니다. 서로소가 아니면 해가 없거나 조건이 겹치므로 다른 방법이 필요합니다.
- 실제 암호에서 쓰는 수백 자리 계산은 큰 정수 연산이 필요합니다. 이 계산기는 원리를 보이기 위한 것입니다.
함께 보면 좋은 도구
마지막 검증: 2026년 8월 30일 · 결과는 참고용 추정치입니다.