거듭제곱 모듈러 계산기란?
거듭제곱 모듈러 계산기는 \((\text{밑}^{\text{지수}}) \bmod m\), 즉 어떤 수를 거듭제곱한 뒤 모듈러스 m으로 나눈 나머지를 구합니다. 이 연산을 '모듈러 지수 연산(modular exponentiation)'이라고 하며, 정수론과 암호학 곳곳에서 핵심 역할을 합니다. RSA 암호화, 디피-헬만(Diffie-Hellman) 키 교환, 소수 판정, 해시 함수 등이 모두 이 연산을 기반으로 합니다. 거대한 거듭제곱을 먼저 계산한 뒤 나머지를 구하는 직접적인 방식은 지수가 커지면 사실상 불가능하므로, 대신 빠른 알고리즘을 사용합니다.
사용 방법
세 개의 정수를 입력하세요. 밑(base), 지수(exponent)(0 또는 양의 정수), 그리고 모듈러스 m(1보다 큰 양의 정수)입니다. 계산 버튼을 누르면 0부터 m−1 사이의 값으로 결과가 나옵니다. 음수 밑을 넣어도 자동으로 적절한 음이 아닌 나머지(잉여, residue)로 변환됩니다.
공식 풀이
이 계산기는 다음 공식을 사용합니다.
$$\text{result} = \text{Base}^{\text{Exponent}} \bmod \text{Modulus}$$
이 계산기는 \(\text{밑}^{\text{지수}}\)라는 거대한 수를 직접 만들지 않고 제곱-곱셈(square-and-multiply) 기법(이진 거듭제곱이라고도 함)을 사용합니다. 먼저 지수를 이진수로 읽습니다. 결과값을 1로 시작해, 밑을 m으로 나눈 나머지를 계속 제곱해 나갑니다. 그리고 현재 보고 있는 지수의 이진 자릿수가 1일 때마다 그 제곱한 값을 누적 결과에 곱하고, 다시 m으로 나눈 나머지를 취합니다. 모든 중간 계산값이 \(m^2\)보다 작게 유지되기 때문에 지수가 수백 자리에 달해도 계산이 매우 빠릅니다.
예제로 보는 계산
\(7^{256} \bmod 13\)을 계산해 봅시다. 13에 대한 7의 위수(order)는 12를 나누며, \(7^{12} \equiv 1\)입니다. \(256 = 12 \times 21 + 4\)이므로 $$7^{256} \equiv 7^{4} = 2401 \equiv 9 \pmod{13}$$가 됩니다. 따라서 답은 9입니다. 217자리나 되는 \(7^{256}\)이라는 수를 전혀 만들지 않고도 즉시 구할 수 있습니다.
자주 묻는 질문(FAQ)
모듈러스가 1이면 어떻게 되나요? 모든 정수는 1에 대해 0과 합동이므로 결과는 0입니다.
지수가 0이어도 되나요? 네. 어떤 수든 0제곱은 1이므로 결과는 \(1 \bmod m\)이 됩니다(\(m > 1\)일 때는 1).
왜 거듭제곱을 그냥 직접 계산하지 않나요? 지수가 크면 중간 계산값의 자릿수가 천문학적으로 늘어나 오버플로가 발생합니다. 매 단계마다 나머지를 취하면 값이 작게 유지되어 훨씬 효율적입니다.
