분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring)

정의

분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring) 은 a^n 을 O(log n) 시간에 계산하는 분할 정복 알고리즘. a^n mod m 같은 모듈러 연산에서 특히 필수적.

재귀 정의:

a^n = (a^(n/2))^2      if n is even
a^n = a · (a^(n/2))^2  if n is odd
a^0 = 1

이진수 표현으로 보면, n의 각 비트마다 제곱을 반복하며 1인 비트만 누적 곱하는 방식.

문제 상황과 동기

a^n mod m 을 구해야 한다. n ≤ 10^18.

• naive: a를 n번 곱한다. O(n). n=10^18 이면 절대 불가능.
• exponentiation by squaring: O(log n). 60회 이하의 곱셈으로 완료.

핵심 통찰: n을 절반으로 나누면 재귀 깊이가 log n. 제곱 한 번으로 지수가 절반이 되므로, 곱셈 횟수는 n의 비트 수에 비례.

RSA, Diffie-Hellman 같은 암호학적 연산 (modular exponentiation), 행렬 거듭제곱 (피보나치 O(log N)), 페르마 소정리 (모듈러 역원) 등 수학/정수론 PS에서 필수.

시각화

핵심 아이디어

invariant: 현재까지 본 비트들로 만든 부분 지수의 거듭제곱 = 누적 곱.

n을 이진수로 보면:

n = b_k 2^k + b_{k-1} 2^{k-1} + ... + b_1 2 + b_0
a^n = a^(b_k 2^k) · a^(b_{k-1} 2^{k-1}) · ... · a^(b_0)

각 a^(2^i) 는 이전 값의 제곱이므로, O(log n) 번의 제곱 + 1인 비트마다 곱셈.

재귀 버전:

exp(a, n):
    if n = 0: return 1
    half = exp(a, n // 2)
    if n % 2 = 0: return half * half
    else:         return a * half * half

반복 버전 (비트마스킹):

result = 1, base = a
while n > 0:
    if n & 1: result *= base
    base *= base
    n >>= 1

알고리즘

재귀 (분할 정복)

exp_mod(a, n, m):
    if n = 0:
        return 1
    half = exp_mod(a, n / 2, m)
    half = (half * half) % m
    if n is odd:
        half = (half * a) % m
    return half

반복 (비트마스킹)

exp_mod_iter(a, n, m):
    result = 1
    base = a % m
    while n > 0:
        if n & 1:
            result = (result * base) % m
        base = (base * base) % m
        n >>= 1
    return result

구현

// 재귀 + 반복 두 가지 구현
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
​
// 재귀
ll exp_mod_rec(ll a, ll n, ll m) {
  if (n == 0) return 1;
  ll half = exp_mod_rec(a, n / 2, m);
  half = (half * half) % m;
  if (n % 2 == 1) half = (half * a) % m;
  return half;
}
​
// 반복
ll exp_mod_iter(ll a, ll n, ll m) {
  ll result = 1, base = a % m;
  while (n > 0) {
      if (n & 1) result = (result * base) % m;
      base = (base * base) % m;
      n >>= 1;
  }
  return result;
}
​
int main() {
  ll a, n, m; cin >> a >> n >> m;
  cout << exp_mod_rec(a, n, m) << "\n";
  cout << exp_mod_iter(a, n, m) << "\n";
}

# Python 내장 pow(a, n, m) 도 같은 알고리즘, O(log n)
# 직접 구현 (반복)
def exp_mod(a, n, m):
  result, base = 1, a % m
  while n > 0:
      if n & 1:
          result = (result * base) % m
      base = (base * base) % m
      n >>= 1
  return result
​
a, n, m = map(int, input().split())
print(exp_mod(a, n, m))
print(pow(a, n, m))  # built-in

// BigInteger.modPow 내부 구현도 동일
import java.util.*;
import java.io.*;
import java.math.BigInteger;
​
public class Main {
  static long expMod(long a, long n, long m) {
      long result = 1, base = a % m;
      while (n > 0) {
          if ((n & 1) == 1) result = (result * base) % m;
          base = (base * base) % m;
          n >>= 1;
      }
      return result;
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      long a = Long.parseLong(st.nextToken());
      long n = Long.parseLong(st.nextToken());
      long m = Long.parseLong(st.nextToken());
      System.out.println(expMod(a, n, m));
      System.out.println(new BigInteger(String.valueOf(a))
          .modPow(BigInteger.valueOf(n), BigInteger.valueOf(m)));
  }
}

2 10 1000000007

1024
1024

3 1000000000000000000 1000000007

101284195
101284195

복잡도

n의 비트 개수만큼만 곱셈. n ≤ 10^18 일 때 ≤ 120회.

변형 / 활용

1. 행렬 거듭제곱

M^n 을 O(log n) 에 계산. 피보나치, 선형 점화식 등 O(log N) 풀이.

typedef vector<vector<ll>> matrix;
matrix mul(matrix A, matrix B, ll m) {
    int n = A.size();
    matrix C(n, vector<ll>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
    return C;
}
matrix mat_exp(matrix M, ll n, ll m) {
    int sz = M.size();
    matrix result(sz, vector<ll>(sz));
    for (int i = 0; i < sz; i++) result[i][i] = 1;
    while (n > 0) {
        if (n & 1) result = mul(result, M, m);
        M = mul(M, M, m);
        n >>= 1;
    }
    return result;
}

2. 모듈러 역원 (페르마 소정리)

m이 소수일 때, a^(-1) ≡ a^(m-2) (mod m).

ll inv(ll a, ll m) {
    return exp_mod(a, m - 2, m);
}

3. 오일러 정리

a^φ(m) ≡ 1 (mod m) (gcd(a, m)=1). a^n mod m = a^(n mod φ(m)) mod m.

함정

1. 오버플로우

(half * half) % m 에서 half가 m-1 이면 곱이 (m-1)^2, long long 범위 초과 가능.

해법: (__int128) 또는 modular multiplication 함수.

ll mul_mod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

2. n=0 처리

a^0 = 1 은 a=0 일 때도 1. edge case 확인.

3. 음수 밑 (a < 0)

모듈러 연산에서 음수는 a = ((a % m) + m) % m 로 정규화.

4. m=1

a^n mod 1 = 0 항상. 예외 처리 안 하면 나눗셈 by zero.

BOJ 연습 문제

참고

• 모듈러 산술
• 페르마 소정리
• 행렬 거듭제곱