모듈러 역원 계산기

결과

모듈러 역원

(a·x) mod m = 1을 만족하는 x

역원 존재 여부	예
gcd(a, m)	1

모듈러 역원이란?

정수 a의 법 m에 대한 모듈러 곱셈 역원은 $(a \cdot x) \bmod m = 1$을 만족하는 정수 x를 말합니다. 모듈러 산술에서 '나눗셈'에 해당하는 연산으로, 정수론은 물론 RSA 암호 시스템과 부호 이론의 여러 알고리즘에서 핵심적인 역할을 합니다. 이 계산기는 확장 유클리드 알고리즘을 사용해 x를 구합니다.

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$

시계 같은 원형 모듈러스 링을 감싸는 수직선에서 a 곱하기 x가 1에 도달하는 모습 — 모듈러 역원 x는 곱하면 a를 다시 1로 되돌리며, 모듈러스 m을 한 바퀴 돕니다.

계산기 사용법

숫자 a와 법 m(단, $m \geq 2$)을 입력하세요. 이 도구는 $0 \leq x < m$ 범위에서 가장 작은 음이 아닌 역원 x를 알려 주고, 역원이 존재하는지 확인해 주며 $\gcd(a, m)$ 값도 함께 표시합니다. 만약 $\gcd(a, m) \neq 1$이면 역원이 존재하지 않으며, 결과는 "없음"으로 표시됩니다.

공식 풀이

역원은 $\gcd(a, m) = 1$일 때, 즉 a와 m이 서로소일 때만 존재합니다. 확장 유클리드 알고리즘은 $a \cdot x + m \cdot y = \gcd(a, m)$을 만족하는 정수 x, y를 찾아 줍니다. gcd가 1이면 x를 법 m으로 나눈 나머지가 곧 역원이 됩니다. 이때 결과가 음수이면 m을 더해 양수 값으로 정규화합니다.

gcd와 계수를 생성하는 확장 유클리드 알고리즘 단계의 평면 순서도 — 확장 유클리드 알고리즘은 gcd(a, m) = 1일 때 역원을 주는 계수를 산출합니다.

예제로 살펴보기

법 11에 대한 3의 역원을 구해 봅시다. $3x \equiv 1 \pmod{11}$을 만족하는 x가 필요합니다. 직접 대입해 보면 $$3 \times 4 = 12 = 11 + 1$$이므로 $12 \bmod 11 = 1$이 됩니다. 따라서 $x = 4$입니다. 확장 유클리드 알고리즘도 동일한 값을 반환하며, $\gcd(3, 11) = 1$이므로 역원이 존재함을 확인할 수 있습니다.