빠른 거 제곱법(exponentiation by squaring)

a^b mod m의 값을 구하는 방법은 거듭제곱의 모듈러 연산으로 불린다.

하지만 일반적인 방법으로는 계산할수 없을정도로 큰 값이 나올 수 있기 때문에 

이를 효율적으로 계산하기 위해서 거듭제곱을 빠르게 계산하는 방법인 모듈러 거듭제곱법 또는 빠른 거듭제곱법을 사용해야한다.

 

빠른 거듭제곱법의 증명을 하기전에 우선 기본적인 모둘러 산술 성질을 알아보자

1. 곱셈의 모듈러 성질:
   • (a*b) mod m = [(a mod m) * (b mod m)] mod m;
2. 거듭제곱의 모듈러 성질:
   • (a^b) mod m = [(a mod m)^b mod m]

 

이 성질들을 활용해서 빠른 거듭제곱법을 설명 할 수 있다.

 

빠른 거듭제곱법은 주어진 지수 b를 이진수로 표현해서 계산을 효율화하는 방법이다.

 

b를 다음과 같이 바꿔서 표현해보자

여기서 ci는 0 또는 1이다.

 

a^b는 다음과 같이 표현할 수 있다.

이 식을 다시 분해하면

가 되고

이제 이 식의 각 항을 모듈러 연산을 통해 계산하면

이런 식으로 표현이 된다. 이제 계산과정을 반복해 보면, b를 반으로 나누며 계산하는 과정이 왜 성립하는지 알 수 있다.

 

 

구체적인 증명과정

• 기본 케이스 : b = 0인 경우
  • a^0 mod m
  • = 1 mod m
  • = 1
• 반복 케이스 : b > 0인 경우
  • b가 홀수라면
    • a^b mod m
    • = (a * a^b-1) mod m
    • = [(a mod m) * (a^b-1 mod m)] mod m
  • b가 짝수라면
    •  a^b mod m
    • = (a^b/2 * a^b/2) mod m
    • = [(a^b/2 mod m) * (a^b/2 mod m)] mod m
• 이렇게 b를 절반으로 줄여가며 계산하면, 시간 복잡도가 획기적으로 줄어들어 O(logb)가 된다.

 

코드 예시

int ModExp(int a, int b, int m)
{
	int result = 1;

	while (b > 0)
	{
		if (b % 2 != 0)
		{
			result = result * a % m;
		}

		a = (a * a) % m;
		b /= 2;
	}

	return result;
}

 

 

결론

빠른 거듭제곱법은 거듭제곱의 이진 분할을 이용해 계산을 최적화하는 방법이다. 이 방법은 위에서 설명한 모듈러 연산의 성질을 기반으로 해서 큰 수의 거듭제곱을 효율적으로 계산할 수 있다.