거듭제곱 계산법

이 문서는 컴퓨터가 거듭제곱을 빠르게 계산하는 방법을 다룬다.

[math]\displaystyle{ a^b }[/math]의 값을 구하려고 할 때, [math]\displaystyle{ a, b }[/math]중 하나가 정수가 아닌 실수이면 계산 결과는 일반적으로 정수가 아니다. 이 경우 [math]\displaystyle{ e^{b\ln a} }[/math]와 같이 변형하거나, 이항급수인 [math]\displaystyle{ (1+x)^b=\sum_{n=0}^{\infty} \binom{b}{n}x^n }[/math] 등으로 테일러 급수를 적용하여 근삿값을 산출한다. 그런데 밑이 정수이고, 지수가 자연수일 때 참값을 직접 출력하고자 한다면, 아래 방법을 이용한다. 이 알고리즘은 [math]\displaystyle{ a }[/math]가 다항식 또는 행렬 등 거듭제곱이 적용되는 어떤 대상이라도 쓸 수 있다.

지수의 이진법 전개

먼저 입력받은 지수를 이진법으로 적는다. 그 다음 각 비트의 값인 0 또는 1에 따라 계산 과정을 결정한다. 이진법 상에서 [math]\displaystyle{ n+1 }[/math]비트라 가정하고, 맨 오른쪽 비트는 0번째로 취급한다.

[math]\displaystyle{ b=\sum_{k=0}^{n} e_k2^k, e_k \in \{0, 1\} }[/math]

[math]\displaystyle{ a^b=\prod_{k=0}^{n} a^{e_k2^k} }[/math]

[math]\displaystyle{ A=\{k: 0 \leq k \leq n, e_k=1\} }[/math]

오른쪽 비트부터 읽기

위 식에서 [math]\displaystyle{ c_k=a^{2^k} }[/math]라 하면 [math]\displaystyle{ a^b=\prod_{k=0}^{n} c_k^{e_k}=\prod_{k \in A}c_k }[/math]와 같이 쓸 수 있다. 한편 [math]\displaystyle{ c_0=a, c_n=c_{n-1}^2 (n \leq 1) }[/math]을 이용하면 주어진 식을 빠르게 셈할 수 있다.

오른쪽 비트부터 읽는 방식은 가장 작은 항인 [math]\displaystyle{ c_0 }[/math]부터 시작해서 제곱을 반복하고, 비트의 값이 1인 항마다 주어진 수에 곱하는 방식이다.

• [math]\displaystyle{ \text{Input }a, n \leftarrow \lfloor \log_2 a \rfloor }[/math]
• [math]\displaystyle{ x \leftarrow 1, c \leftarrow a, k \leftarrow 0 }[/math]
• [※] [math]\displaystyle{ e_k=1 }[/math]이면 [math]\displaystyle{ x \leftarrow cx }[/math]
• [math]\displaystyle{ k=n }[/math]이면 여기서 알고리즘을 종료하고 [math]\displaystyle{ x }[/math]를 반환한다.
• [math]\displaystyle{ c \leftarrow c^2, k \leftarrow k+1 }[/math] 다음 [※]로 돌아간다.

예를 들어 3의 13제곱을 셈하고자 한다면, 13을 이진법인 1101₍₂₎과 같이 적고, 비트를 맨 오른쪽부터 읽어서 1, 0, 1, 1 순으로 적용한다.

a=3, n=3, x=1, c=3, k=0
e={1, 0, 1, 1}
e[0]==1: x=c*x ##x=3
c=c*c, k=k+1 ##c=9, k=1
e[1]==0: pass
c=c*c, k=k+1 ##c=81, k=2
e[2]==1: x=c*x ##x=243
c=c*c, k=k+1 ##c=6561, k=3
e[3]==1: x=c*x ##x=1594323
k==3: END

최종 결과: 1594323

왼쪽부터 비트 읽기

이번에는 지수의 비트를 반대로 가장 큰 자리부터 읽는다. [math]\displaystyle{ a^r=\begin{cases}(a^{\frac{n}{2}})^2 &\text{if } 2 \mid r \\ a\cdot (a^{\frac{n-1}{2}})^2 &\text{if } 2 \nmid r \end{cases} }[/math]을 이용하여 아래 수열을 정의한다.

[math]\displaystyle{ x_0=a, x_{k+1}=\begin{cases}x_{k-1}^2 &\text{if } e_{n-k}=0 \\ ax_{k-1}^2 &\text{if } e_{n-k}=1 \end{cases} }[/math]

이렇게 식을 세우면 [math]\displaystyle{ x_n=a^b }[/math]에 도달하며, 알고리즘은 아래와 같이 세울 수 있다.

• [math]\displaystyle{ \text{Input }a, n \leftarrow \lfloor \log_2 a \rfloor }[/math]
• [math]\displaystyle{ x \leftarrow 1, j \leftarrow n }[/math]
• [math]\displaystyle{ e_j=1 }[/math]이면 [math]\displaystyle{ x \leftarrow ax }[/math]
• [※] [math]\displaystyle{ x \leftarrow x^2, j \leftarrow j-1 }[/math]
• [math]\displaystyle{ j=0 }[/math]이면 여기서 알고리즘을 종료하고 [math]\displaystyle{ x }[/math]를 반환한다. 그렇지 않으면 [※] 지점으로 돌아간다.

이번에는 3의 13제곱을 왼쪽부터 읽는 방식으로 계산해본다. 이번에는 비트를 위 예시와는 반대로 맨 왼쪽부터 1, 1, 0, 1 순으로 읽는다.

a=3, n=3, x=1, j=3
e={1, 0, 1, 1}
e[3]==1: x=a*x ##x=3
x=x*x, j=j-1 ##x=9, j=2
e[2]==1: x=a*x ##x=27
x=x*x, j=j-1 ##x=729, j=1
e[1]==0: pass
x=x*x, j=j-1 ##x=531441, j=0
e[0]==1: x=a*x ##x=1594323
j==0: END

최종 결과: 1594323

모듈러 연산

모듈러산술에서 거듭제곱을 셈할 때에는 상술한 알고리즘에서 모든 곱셈을 곱셈 후 나머지 연산으로 치환하면 된다. 정수론 영역 중 소수판정법에서 이 연산을 많이 적용한다. 대표적으로 페르마의 소정리, 프로트의 정리, 밀러-라빈 소수판정법, 포클링턴-레머 소수판정법 등 [math]\displaystyle{ a^b \mod p }[/math] 꼴의 식을 계산하는 알고리즘에서 유용하게 쓰인다. 또, 소인수분해 중 폴라드 p-1 소인수분해법에서도 마찬가지로 쓸 수 있다.