모듈러 곱셈 역원(modulo m)이란?
정수 a의 법 m에 대한 모듈러 곱셈 역원은 \((a \cdot x) \bmod m = 1\)을 만족하는 1부터 m−1 사이의 정수 x를 말합니다. 쉽게 말해 a와 x를 곱한 뒤 m으로 나누면 나머지가 정확히 1이 되는 값입니다. 이는 모듈러 연산에서 'a로 나누기'에 해당하는 개념으로, 정수론과 암호학(RSA 키 생성, 해싱, 중국인의 나머지 정리 등)의 핵심 도구입니다.
계산기 사용법
정수 a와 법 m(m은 2 이상이어야 합니다)을 입력하세요. 계산기는 a를 m으로 나눈 나머지로 정리한 뒤 확장 유클리드 알고리즘을 실행하여, 역원이 존재한다면 그 값을 반환합니다. a가 음수일 경우에도 자동으로 0부터 m−1 범위로 환산하여 처리합니다.
공식 설명
역원은 오직 \(\gcd(a, m) = 1\)일 때만 존재합니다. 즉 a와 m이 1 외에 공약수를 갖지 않을 때(서로소일 때)입니다. 확장 유클리드 알고리즘은 다음을 만족하는 정수 s와 t를 찾아냅니다.
$$a \cdot s + m \cdot t = \gcd(a, m)$$gcd가 1일 때, 계수 s를 법 m으로 환산한 값이 바로 역원입니다. \(\gcd(a, m) \neq 1\)이라면 역원은 존재하지 않습니다.
예제 풀이
법 11에 대한 3의 역원을 구해 봅시다. \((3 \cdot x) \bmod 11 = 1\)을 만족하는 x가 필요합니다. 직접 따져 보면 다음과 같습니다.
$$3 \cdot 4 = 12, \quad 12 \bmod 11 = 1$$이므로 역원은 4입니다. \(\gcd(3, 11) = 1\)이므로 확장 유클리드 알고리즘도 즉시 동일한 결과를 내놓습니다.
자주 묻는 질문
역원이 존재하지 않는 경우는 언제인가요? a와 m이 서로소가 아닐 때입니다. 예를 들어 4는 법 8에서 역원이 없는데, \(\gcd(4, 8) = 4 \neq 1\)이기 때문입니다.
법(m)이 반드시 소수여야 하나요? 아닙니다. a가 m과 서로소이기만 하면 어떤 법이든 사용할 수 있습니다. 다만 m이 소수라면 1부터 m−1까지의 모든 0이 아닌 a가 역원을 가집니다.
결과는 왜 항상 1과 m−1 사이인가요? 역원을 법 m으로 환산하여 가장 작은 양의 대표값을 표준으로 제시하기 때문입니다.
