거듭제곱 형태의 나머지를 log n만에 계산하는 방법

1. Introduction

$a^b \bmod m$형태를 계산하는 방법은 여기에 포스팅했다.

이번 포스팅에서는 이것을 돌리기 위한 코드를 최적화하는 방법을 소개한다.

2. Approach

$a^b$의 형태의 자연수에 대한 나머지 계산에 대한 방법들을 소개한다.

2.1 일반적인 방법

def powMod1(base, index, mod):
    r = 1
    for i in range(index):
        r *= base
        r %= mod
    return r

시간복잡도가 $O(b)$이다. r이 $a^b$까지 커지기 때문에 overflow일어나기 매우 쉽다.

2.2 개선된 방법

def powMod2(base, index, mod):
    if index == 1:
        return base
    if index % 2 == 0:
        r = powMod2(base, index // 2, mod)
        return (r ** 2) % mod
    else:
        return (base * powMod2(base, index - 1, mod)) % mod

합동식 연산의 특성을 이용한 방법이다. 시간복잡도가 $O(log \; b)$으로 줄어든다.

2.3 최적화

def powMod3(base, index, mod):
    r = 1
    while index:
        if index & 1:
            r = (r * base) % mod
        base = (base ** 2) % mod
        index >>= 1
    return r

재귀를 반복문으로 고치고, 비트연산자를 사용한다.