지수를 쪼개기
13=8+4+1이므로 a¹³=a⁸a⁴a다. a²를 구하고 이를 제곱해 a⁴, 다시 제곱해 a⁸을 만든다. 지수의 이진 표현에서 1인 자리에 해당하는 값만 결과에 곱한다.
짝수와 홀수의 관계
a²ᵏ=(aᵏ)²이고 a²ᵏ⁺¹=a(aᵏ)²이다. 지수를 절반으로 줄이는 같은 구조를 반복할 수 있다. 0이 아닌 a에서 지수가 0이면 결과는 1로 두어 계산의 시작점으로 사용한다.
나머지 계산
법 17에서 3²≡9, 3⁴≡13, 3⁸≡16이다. 따라서 3¹³≡16×13×3≡12 (mod 17)이다. 매 곱셈 뒤 나머지를 취하면 큰 거듭제곱의 전체 값을 저장할 필요가 없다.
연산 수와 실제 비용
O(log n)은 곱셈 연산의 횟수를 나타낸다. 큰 정수를 정확히 계산하면 피연산자의 자릿수도 커지므로 실제 비트 연산 시간까지 무조건 같은 복잡도인 것은 아니다. 나머지 계산에서는 법의 크기도 비용에 영향을 준다.
관련 문서
거듭제곱 / 이진법 / 알고리즘 / 합동식 / 나머지 / 오일러 정리 (정수론) / 페르마의 소정리 / 시간 복잡도