본문 바로가기

컴퓨터/Python

거듭제곱 계산하기

RSA 암호화를 하는 과정에 있어서 거듭 제곱을 계산할 필요가 있습니다.


$a^n$을 계산할 때 for이나 while 문과 같이 반복문을 이용해서 $n$번을 곱하는 방법이 가장 쉽게 생각할 수 있는 방법입니다.


def easy_mod_pow(base, exp, mod):
	base %= mod
	result = 1
	while exp > 0:
		result = (result * base) % mod;
		exp -= 1
	return result


이 알고리즘의 경우에는 시간 복잡도를 생각하면 $O(n)$이라는 것을 알 수 있습니다. (반복문이 n번 돌기 때문) 즉 $n$의 값이 크면 그 만큼 속도가 느려진다는 것을 의미하고, RSA 암호화 과정에서는 $n$의 값을 큰 것으로 사용하기 때문에 이러한 방법으로는 어렵다는 것을 알 수 있습니다.


Divide & Conquer 방법으로 이 문제를 접근해서 Recursive로 코드를 작성하면 아래와 같습니다.


def rec_mod_pow(base, exp, mod):
	base %= mod
	if exp == 0:
		return 1
	elif exp == 1:
		return base
	t = rec_mod_pow(base, exp >> 1, mod)
	t = (t * t) % mod
	if exp & 1 != 0:
		return (t * base) % mod
	else:
		return t


이제 이것을 Recursive가 아닌 반복문으로 바꾸어서 작성해보면 아래와 같습니다.


def opt_mod_pow(base, exp, mod):
	base %= mod
	result = 1
	while exp > 0:
		if exp & 1 != 0:
			result = (result * base) % mod
		base = (base * base) % mod;
		exp >>= 1
	return result


즉 이렇게 하면 시간 복잡도가 $O(\log_{2} n)$이라는 것을 알 수 있습니다.


참고로 Python의 경우에는 큰 숫자를 다루는데에 있어서 다른 언어에 비해서 제약이 적기 때문에 RSA 암호화에서 사용하는 정도에는 크게 무리가 없습니다.