모듈러 거듭제곱이란?
모듈러 거듭제곱은 \(a^b \bmod m\), 즉 거듭제곱 \(a^b\)를 법 m으로 나누었을 때 남는 나머지를 구하는 연산입니다. 정수론과 암호학에서 가장 중요한 연산 중 하나로, RSA, 디피–헬먼 키 교환, 전자 서명 같은 알고리즘의 핵심을 이룹니다. \(a^b\)가 천문학적으로 커지더라도 m으로 나눈 나머지는 작은 값으로 유지되어 계산할 수 있습니다.
계산기 사용법
세 개의 정수를 입력하세요. 밑 a, 0 이상의 지수 b, 그리고 법 m(양의 정수)입니다. 계산 버튼을 누르면 0부터 \(m-1\) 사이의 나머지 하나가 나옵니다. 밑은 음수여도 괜찮습니다. 음수 밑은 거듭제곱 전에 먼저 유효한 나머지 범위로 정규화됩니다.
공식 풀이
\(a^b\)를 직접 계산하는 것은 b가 클 때 불가능하므로, 이 도구는 제곱-곱셈(square-and-multiply) 기법(빠른 거듭제곱 또는 이진 거듭제곱이라고도 함)을 사용합니다. 지수를 이진수로 읽어 나갑니다. 결과 \(r = 1\)과 m으로 나눈 밑에서 시작해, 지수의 각 비트마다 밑을 제곱(mod m)하고, 현재 비트가 1일 때마다 결과에 밑을 곱합니다(mod m). 이 방법은 b번이 아니라 약 \(\log_2(b)\)번의 곱셈만 필요합니다.
풀이 예제
\(4^{13} \bmod 497\)을 계산해 봅시다. 지수 13을 이진수로 나타내면 1101입니다. 제곱-곱셈을 차례로 따라가면: $$4^1 = 4, \quad 4^2 = 16, \quad 4^4 = 256, \quad 4^8 = 256^2 = 65536 \equiv 30 \pmod{497}.$$ \(13 = 8 + 4 + 1\)이므로 해당하는 거듭제곱들을 곱하면: $$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}.$$ 따라서 \(4^{13} \bmod 497 = \mathbf{445}\)입니다.
자주 묻는 질문
지수가 0이면 어떻게 되나요? 어떤 수든 0제곱은 1이므로 결과는 \(1 \bmod m\)입니다(\(m = 1\)일 때는 0이 됩니다).
밑이 음수여도 되나요? 네. 음수 밑은 먼저 m에 대한 동등한 양의 나머지로 변환되므로, 답은 항상 0과 \(m-1\) 사이입니다.
그냥 \(a^b\)를 구한 다음 나머지를 취하면 안 되나요? 암호학적 크기에서는 \(a^b\)가 수백만 자리에 달합니다. 매 단계마다 m으로 나눈 나머지를 취하면 숫자가 작게 유지되어 계산이 빨라집니다.
