이진 거듭제곱(Binary Exponentiation)

shjk·2025년 5월 27일

이진 거듭제곱(Binary Exponentiation)은 거듭제곱 연산인 $a^n$ 을 빠르게 계산하기 위한 알고리즘으로, 지수를 이진수로 표현하여 효율적으로 계산하는 방식이다. 이 방법은 특히 큰 지수 $n$ 을 빠르게 처리하는 데 유용하다.

1. 기본 개념

일반적으로 거듭제곱 $a^n$ 은 다음과 같이 표현할 수 있다.

a^n = \underbrace{a \times a \times \dots \times a}_{n\text{개}}

하지만 이 방식은 시간복잡도가 $O(n)$ 이 되어, 지수 $n$ 이 커지면 비효율적이다.
이진 거듭제곱법은 이를 최적화하여 $O(\log n)$ 에 수행한다.

이 알고리즘은 다음의 두 가지 원칙에 근거한다.

$a^{2k} = (a^k)^2$
$a^{2k+1} = a \times (a^k)^2$

2. 알고리즘 원리

이진 거듭제곱의 핵심은 지수 $n$ 을 이진수로 표현한 뒤, 그 비트를 따라 계산하는 것이다.
예를 들어, $n = 13$ 이라고 하면, 이를 이진수로 나타내면 $1101_2$ 가 된다.

13_{10} = 1101_2 = 2^3 + 2^2 + 2^0

따라서 다음과 같은 방식으로 계산할 수 있다.

a^{13} = a^{8 + 4 + 1} = a^8 \times a^4 \times a^1

즉, $a$ 의 제곱을 반복해서 계산하며, 필요한 부분만 곱하여 결과를 얻는다.

3. 알고리즘 과정

이진 거듭제곱의 절차는 다음과 같다.

결과값(result)을 1로 초기화한다.
지수 $n$ 의 이진수를 끝에서부터 순회하면서:
- 현재 비트가 1이면, result에 현재의 $a$ 를 곱한다.
- $a$ 를 $a \leftarrow a^2$ 로 갱신한다. (다음 비트로 넘어갈 때마다)
모든 비트를 처리하면, 최종 result가 $a^n$ 이 된다.

의사 코드 (Pseudo Code)

function binary_exponentiation(a, n):
    result ← 1
    while n > 0:
        if (n mod 2) = 1:
            result ← result × a
        a ← a × a
        n ← ⌊n / 2⌋
    return result

4. 시간 복잡도 분석

이진 거듭제곱은 각 반복에서 지수 $n$ 을 절반씩 줄여나가므로, 총 반복 횟수는 $\log_2 n$ 이다.
따라서 이 알고리즘의 시간 복잡도는 다음과 같다.

O(\log n)

5. 실제 구현 예시 (Python)

다음은 파이썬으로 구현한 예시이다.

def binary_exponentiation(a, n):
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= a
        a *= a
        n //= 2
    return result

# 예시 사용법
print(binary_exponentiation(2, 13))  # 출력: 8192

6. 응용 분야

이진 거듭제곱법은 특히 다음과 같은 경우에 유용하다.

모듈러 지수(modular exponentiation): 암호학에서 널리 사용됨
- 예시: RSA 알고리즘에서 암호화/복호화 연산 수행
큰 수의 거듭제곱 계산 시 시간 최적화가 필요한 경우
행렬 거듭제곱 등 반복 연산이 많은 수학 및 알고리즘 문제에서의 최적화

7. 모듈러 지수 예시

큰 숫자의 지수를 계산할 때 중간 결과가 매우 커지는 것을 막기 위해 모듈러 연산을 함께 사용한다.

예를 들어 $a^n \mod m$ 은 중간 연산 단계마다 mod 연산을 수행하면 된다.

def binary_exponentiation_mod(a, n, mod):
    result = 1
    a %= mod
    while n > 0:
        if n % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        n //= 2
    return result

# 예시 사용법
print(binary_exponentiation_mod(2, 13, 1000))  # 출력: 192