1. Introduction
정수론과 암호학을 공부하다보면, 매우 큰 수에 대해 나머지를 알아야 하는 경우가 생긴다. 그 수가 소인수분해가 된다면 나머지를 얻어내는데 큰 어려움이 없겠지만, 그렇지 않다면 그 수를 $N = a^b + R$의 형태로 나누어 계산해야한다.
$a^b$의 나머지를 알 수 있으면 $R$은 상대적으로 작은 수이기 때문에 나머지를 얻어내는데 큰 어려움을 갖지 않는다. 따라서 이번 포스팅에서는 $a^b$의 나머지를 찾아내는 방법을 알아보도록 한다.
2. Approach
기본적인 아이디어는 $ab \bmod m = (a \bmod m)(b \bmod m) \bmod m$에서 착안한다.
지수를 2의 거듭제곱의 합 형태로 나타내어 표현하는 것이다.
$5^{117} \bmod 19$를 예로 들면,
$117_{(10)} = 1110101_{(2)}$이므로 다음이 성립한다.
$$ \begin{matrix}
5^{117} \bmod 19 &=& 5^{2^0+2^2+2^4+2^5+2^6} \bmod 19\\
&=& (5^1*5^4*5^{16}*5^{32}*5^{64}) \bmod 19 \end{matrix}$$
2의 거듭제곱으로 표현된 항에 대해서는 이전의 계산한 결과를 제곱하면 되기 때문에 계산이 용이하다.
