한양과기고 에듀테크 수업도구 대시보드

빠른 거듭제곱 (Fast Exponentiation)

aⁿ 을 구하려면 a × a × … × a 처럼 곱셈을 n − 1번 하면 된다. n이 10억쯤 되면 이 방법은 사실상 끝나지 않는다. 빠른 거듭제곱(square-and-multiply, 분할 정복 거듭제곱)은 지수를 절반으로 접어가며 곱셈 횟수를 약 log₂n번으로 줄인다 — n = 10억이면 60번 이하. 핵심 아이디어 두 줄:

aⁿ = (a^n/2)² (n이 짝수) | aⁿ = a · (a^(n-1)/2)² (n이 홀수)

다르게 보면, 지수 n을 2진수로 쓰고 a¹, a², a⁴, a⁸, … (계속 제곱)을 만들어 두었다가, 비트가 1인 자리의 값만 골라 곱하면 된다. RSA·디피–헬만·해시·모듈러 역원 등 큰 수의 거듭제곱이 필요한 거의 모든 곳에서 쓰인다.

square-and-multiply 한 걸음씩 — 지수의 비트를 훑기

밑 a 3

지수 n 13

n = ₍₂₎ · 낮은 자리(오른쪽)부터 훑는다. 매 단계: 비트가 1이면 현재 base 를 결과에 곱하고, 그 다음 base 를 제곱한다.

단계	비트	base = a^2ᵏ	동작	result

빠른 거듭제곱 곱셈

단순 반복 곱셈 (n−1)

결과 aⁿ

–

슬라이더로 a와 n을 정하고 한 단계를 눌러 보세요.

곱셈 횟수: n−1 vs 약 2·log₂n

단순 반복은 지수 n에 정비례(빨간 직선) — n이 커지면 감당 불가.
빠른 거듭제곱은 로그(초록 곡선) — n을 10배 늘려도 곱셈은 3~4번만 더 는다.
n = 1,000,000,000 → 단순 반복 10억 번, 빠른 거듭제곱 약 45번.

모듈러 거듭제곱 — RSA·디피–헬만이 실제로 하는 계산

암호에서는 aⁿ mod m 이 필요하다. aⁿ 을 다 계산하면 자릿수가 수백만 개가 되지만, 매 곱셈마다 곧바로 mod 를 취하면 수가 항상 m보다 작게 유지된다. 곱하기 전에 접든, 곱한 뒤에 접든 결과가 같다는 모듈러 산술의 성질 덕분이다: (x·y) mod m = ((x mod m)·(y mod m)) mod m.

a n m

비트	base mod m	result mod m

a, n, m 을 넣고 계산.

모든 중간값이 m 미만 — 64비트 정수로도 안전하게 계산.
RSA 복호화는 c^d mod N, d와 N이 2048비트 → square-and-multiply로 약 3000번 곱셈이면 끝.
단순 반복이라면 2²⁰⁴⁸ 번 — 우주가 끝나도 안 끝난다.

알고리즘 — 반복 버전과 재귀 버전

# 반복(iterative) — 지수의 비트를 낮은 자리부터
def power(a, n, m=None):
    result = 1
    base = a if m is None else a % m
    while n > 0:
        if n & 1:                 # 현재 최하위 비트가 1이면
            result *= base
            if m: result %= m
        base *= base                # base 를 제곱: a^1 -> a^2 -> a^4 ...
        if m: base %= m
        n >>= 1                    # 지수를 오른쪽으로 한 칸 (n //= 2)
    return result

# 재귀(divide and conquer)
def power_rec(a, n):
    if n == 0: return 1
    half = power_rec(a, n // 2)
    return half * half * (a if n & 1 else 1)

비트당 최대 2번 곱셈(제곱 1 + 필요시 곱 1) → 전체 O(log n) 곱셈, 재귀 깊이도 log n.
같은 트릭이 행렬 거듭제곱에도 그대로 → 피보나치 n번째 항을 O(log n)에 계산.
Python pow(a, n, m), Java BigInteger.modPow 가 내부에서 바로 이 알고리즘을 쓴다.

정리 — 두 방법 비교

	단순 반복	빠른 거듭제곱
곱셈 횟수	n − 1	≤ 2·⌊log₂n⌋
시간 복잡도	O(n)	O(log n)
추가 메모리	O(1)	O(1) 반복 / O(log n) 재귀
n = 2³⁰ 일 때	≈ 10.7억 번	≈ 45 번
쓰이는 곳	작은 지수	RSA, 디피–헬만, 해시, 행렬 거듭제곱, 조합론 mod p