두 양수 A, B에 대해, A^B라는 큰 거듭제곱수를 생각해보자. 예를 들면 66^77 말이다.
이렇게 큰 수에 대해 나머지 연산(modulo, %)을 빠르게 하는 방법은 다음의 특징을 이용한다.
(a * b) % n = ((a % n) * (b % n)) % n
예제
66^77의 13에 대한 나머지 연산은 다음과 같다.
66^77 % 13
= ((66^2 % 13)^38 * 66) % 13
= (1^38 * 66) % 13
= 66 % 13
= 1
66^77의 89에 대한 나머지 연산은 다음과 같다.
66^77 % 89
= ((66^2 % 89)^38 * 66) % 89
= (84^38 * 66) % 89
= ((84^2 % 89)^19 * 66) % 89
= (25^19 * 66) % 89
= ((((25^2 % 89)^9 * 25) % 89) * 66) % 89
= (((2^9 * 25) % 89) * 66) % 89
= (73 * 66) % 89
= 12
C언어 예제
반복문을 이용하는 방법과 재귀적 호출을 이용하는 방법으로 구현해보았다.
#include<stdio.h>
int exponentation_modulo_loop(int b, int e, int n)
{
int m = 1;
// handle exception
if (b <= 0 || e < 0 || n <= 0)
{
printf("error\n");
exit(-1);
}
if (e == 0) return 1;
b = b % n;
while (e > 1)
{
if (e % 2 == 1)
m = (m * b) % n;
b = (b * b) % n;
e /= 2;
}
return (b * m) % n;
}
int exponentation_modulo_recursion(int b, int e, int n)
{
// handle exception
if (b <= 0 || e < 0 || n <= 0)
{
printf("error\n");
exit(-1);
}
b = b % n;
if (e == 0) return 1;
if (e == 1) return b;
b = exponentation_modulo_recursion(b * b, e / 2, n) * ((e & 1) == 1 ? b : 1);
return b % n;
}
int main(void)
{
int b, e, n;
printf("Input positive numbers b, e, and n for calculate [ b^e %% n ]\n");
scanf("%d %d %d", &b, &e, &n);
printf("%d^%d %% %d = %d\n", b, e, n, exponentation_modulo_recursion(b, e, n));
printf("%d^%d %% %d = %d\n", b, e, n, exponentation_modulo_loop(b, e, n));
}단 int형을 다루도록 되어있기 때문에 n이 46341(INT_MAX의 제곱근보다 큰 정수의 최소값)보다 큰 경우 b * b 부분에서 오버플로우가 일어날 가능성이 있다.
