모듈러 곱셈 역원 계산기란?
이 계산기는 정수 a의 모듈로 m 곱셈 역원, 즉 \(a \cdot x \equiv 1 \pmod{m}\)을 만족하는 \(0 \le x < m\) 범위의 유일한 정수 x를 찾아 줍니다. 계산에는 확장 유클리드 호제법(Extended Euclidean Algorithm)을 사용하며, 이 과정에서 최대공약수 \(\gcd(a, m)\)도 함께 구합니다. 이것은 순수한 정수론으로 어느 나라에서나 동일하게 적용되며, 암호학(RSA 키 생성), 해싱, 일차 합동식 풀이 등에서 폭넓게 쓰입니다.
사용 방법
정수 a와 양의 법(모듈러스) m을 입력하세요. 의미 있는 유일한 역원을 얻으려면 \(m \ge 2\)를 사용합니다. 계산기는 a를 m으로 나눈 나머지로 줄인 뒤 확장 유클리드 호제법을 실행하여, 역원과 함께 \(\gcd(a, m)\)를 보여 줍니다. 만약 a와 m이 서로소가 아니라면(\(\gcd \ne 1\)) 역원이 존재하지 않으며, 이 경우 계산기가 그 사실을 알려 줍니다.
공식 설명
역원은 \(\gcd(a, m) = 1\)일 때, 그리고 오직 그때에만 존재합니다. 확장 유클리드 호제법은 \(a \cdot s + m \cdot t = \gcd(a, m)\)을 만족하는 정수 s와 t를 찾아 줍니다. gcd가 1이면 \(a \cdot s \equiv 1 \pmod{m}\)이 성립하므로, 역원은 다음과 같이 가장 작은 음이 아닌 나머지로 정규화한 값입니다.
$$x = ((s \bmod m) + m) \bmod m$$
풀이 예시
a = 7, m = 4인 경우: \(7 \equiv 3 \pmod 4\)이므로 \(3x \equiv 1 \pmod 4\)을 풀면 됩니다. (7, 4)에 확장 유클리드 호제법을 적용하면 gcd = 1, 베주 계수 s = -1이 나오므로 다음과 같습니다.
$$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$
검산: \(7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod 4\). 따라서 답은 3입니다.
자주 묻는 질문
역원이 존재하지 않는 경우는 언제인가요? \(\gcd(a, m) > 1\)일 때뿐입니다. 예를 들어 a = 6, m = 9는 gcd = 3이므로 역원이 존재하지 않습니다.
a가 음수이거나 m보다 클 수도 있나요? 네, 가능합니다. 먼저 a를 m으로 나눈 나머지로 줄이는데, \(a \equiv a' \pmod{m}\)이므로 결과는 달라지지 않습니다.
m = 1이면 어떻게 되나요? 모든 정수는 모듈로 1에서 0과 합동이므로, 역원은 자명하게 0입니다.
