거듭제곱(나머지) 계산하기

$a^n (mod m)$를 구하는 문제는 RSA 암호 등에서 사용되며 그 중요성이 크다.

단순히 곱해주는 방법이 가장 기본적이겠지만, 분할 정복을 사용하면 더 효율적으로 구하는 것이 가능하다.

보통 오래 걸리는 큰 숫자에서는 mod를 사용하지만, 나머지가 아닌 진짜 수를 원한다면 코드에서 mod 부분을 없애면 된다.

1. 기본적인 방법

숫자를 곱하며 mod 해주는 것을 n회 반복한다.

시간 복잡도는 $O(n)$이다.

int pow1(int base, int index, int mod = 10) {
	long long r = 1;
	for (int i = 0; i < index; ++i) {
		r *= base;
		r %= mod;
	}
	return r;
}

2. 분할 정복

$a^{2n} = (a^n)^2$이라는 점에 착안한다.

n이 홀수일 경우 1을 빼고, n이 짝수일 경우 2로 나누어준다.

시간 복잡도는 $O(\log n)$으로 바뀐다.

int pow2(long long base, int index, int mod = 10) {
	if (index == 1) return base;
	if (index % 2 == 0) {
		long long r = pow2(base, index / 2, mod);
		return (r * r) % mod;
	}
	else {
		return (base * pow2(base, index - 1, mod)) % mod;
	}
}

3. 최적화된 코드

위에서의 코드는 재귀함수를 사용하여 그 속도가 다소 느릴 수 있다. while문을 사용하여 속도를 상승시키고, 연산자도 비트 연산자로 교체하였다.

int pow3(long long base, int index, int mod = 10) {
	long long r = 1;
	while (index != 0) {
		if (index & 1) r = (r * base) % mod;
		base = (base * base) % mod;
		index >>= 1;
	}
	return r;
}