📂정수론

연속제곱법 증명

알고리즘

자연수 $a,k,m$ 에 대해 $b \equiv a^{k} \pmod{m}$ 를 다음과 같이 계산할 수 있다.

---

Step 1. $k$ 의 이진법 전개

$u_{i} = 0$ 혹은 $u_{i} = 1$ 에 대해 다음과 같이 나타낸다. $$ k = \sum_{i=0}^{r} u_{i} 2^{i} = u_{0} + 2 u_{1} + \cdots + 2^r u_{r} $$

---

Step 2.

$$ \begin{align*} a & & & \equiv A_{0} \pmod{m} \\ a^{2} & \equiv ( a^1 )^2 & \equiv A_{0}^2 & \equiv A_{1} \pmod{m} \\ a^{4} & \equiv ( a^2 )^2 & \equiv A_{1}^2 & \equiv A_{2} \pmod{m} \\ a^{8} & \equiv ( a^4 )^2 & \equiv A_{2}^2 & \equiv A_{3} \pmod{m} \\ & & & \vdots \end{align*} $$ 위와 같이 $a^{2^{r}} \equiv ( a^{2^{r-1}} )^2 \equiv A_{r-1}^2 \equiv A_{r} \pmod{m}$ 를 계산한다.

---

Step 3.

$A_{0}^{u_{0}} \cdot A_{1}^{u_{1}} \cdot \cdots A_{r}^{u_{r}}$ 을 계산하면 다음을 얻는다. $$ a^{k} \equiv A_{0}^{u_{0}} \cdot A_{1}^{u_{1}} \cdot \cdots A_{r}^{u_{r}} \pmod{m} $$

설명

컴퓨터의 발전으로 거듭제곱의 계산도 빠르게 할 수 있는 시대가 왔지만 인간은 만족을 모른다. 연속제곱법은 모듈러 연산에 무지막지하게 큰 숫자를 직접 구하지 않고도 그 답을 내주는 방법이다. 한번 제곱할때마다 $\pmod{m}$ 으로 나눠주기 때문에 수가 $m$ 이하로 떨어져서 계산량이 줄어드는 것이다.

예제

예를 들어 $7^{327} \pmod{853}$ 을 구한다고 해보자. $7^{327}$ 에 상용로그를 취하면 $327 \log 7 \approx 327 \cdot 0.8450 = 276.315$ 이므로 자릿수만 무려 $277$ 인 큰 수다. 정직하게 다 곱해서 나눗셈을 하기엔 너무 크니까 위의 알고리즘을 사용해보자. 일단 위의 알고리즘대로 $327$ 를 이진법 전개하면 다음과 같다. $$ 327 = 256 + 64 + 4 +2 +1 = 2^{8} + 2^{6} + 2^2 + 2^1 + 2^0 $$ Step 2대로 계산해보면 $$ \begin{align*} 7 & & \equiv 7 & \equiv 7 \pmod{853} \\ 7^{2} & \equiv ( 7^1 )^2 & \equiv 7^2 & \equiv 49 \pmod{853} \\ 7^{4} & \equiv ( 7^2 )^2 & \equiv 49^2 & \equiv 2401 \equiv 695 \pmod{853} \\ 7^{8} & \equiv ( 7^4 )^2 & \equiv 695^2 & \equiv 227 \pmod{853} \\ 7^{16} & \equiv ( 7^8 )^2 & \equiv 227^2 & \equiv 349 \pmod{853} \\ 7^{32} & \equiv ( 7^{16} )^2 & \equiv 349^2 & \equiv 675 \pmod{853} \\ 7^{64} & \equiv ( 7^{32} )^2 & \equiv 675^2 & \equiv 123 \pmod{853} \\ 7^{128} & \equiv ( 7^{64} )^2 & \equiv 123^2 & \equiv 628 \pmod{853} \\ 7^{256} & \equiv ( 7^{128} )^2 & \equiv 628^2 & \equiv 298 \pmod{853} \end{align*} $$ 따라서 $$ 7^{327} = 7^{256} \cdot 7^{64} \cdot 7^{4} \cdot 7^{2} \cdot 7^{1} = 298 \cdot 123 \cdot 695 \cdot 49 \cdot 7 \equiv 286 \pmod{853} $$ 이다. 이 방법도 힘들다고 느낄 수는 있겠지만, 그냥 $327$ 번을 일일이 곱하는 것에 비하면 아주 해봄직한 계산량이다.

증명

$$ \begin{align*} a^{k} =& a^{u_{0} + 2u_{1} + \cdots + 2^r u_{r} } \\ =& a^{u_{0}} a^{ 2u_{1} } \cdots a^{ 2^r u_{r} } \\ \equiv & A_{0}^{u_{0}} A_{1}^{u_{1}} \cdots A_{r}^{u_{r}} \pmod{m} \end{align*} $$

■

코드

아래는 연속제곱법으로 $7^{327} \pmod{853}$ 구하는 예제 코드로, R 언어로 작성되었다. 참고로 power 옵션은 음의 정수에도 대응되며, mod가 소수라면 power=-1을 입력함으로써 주어진 base의 곱셈에 대한 역원을 구할 수 있다.

FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
  i<-0
  if (power<0) {
    while((base*i)%%mod != 1) {i=i+1}
    base<-i
    power<-(-power)}
  
  if (power==0) {return(1)}
  if (power==1) {return(base%%mod)}
  
  n<-0
  while(power>=2^n) {n=n+1}
  
  A<-rep(1,n)
  A[1]=base
  
  for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
  
  for(i in n:1) {
    if(power>=2^(i-1)) {power=power-2^(i-1)}
    else {A[i]=1} }
  
  for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
  
  return(A[1])
}
 
FPM(7,327,853)
FPM(7,-1,11)