##
마지막으로 거듭제곱의 성질에 대해 알아봅시다.

A^B mod C = ( (A mod C)^B ) mod C

A^B mod C를 계산할 때 B가 큰 값인 경우가 종종 있습니다.
안타깝게도 B가 그다지 크지 않은 값일 때조차도 A^B는 굉장히 커집니다.

예를 봅시다:

2^90 = 1,237,940,039,290,000,000,000,000,000
7^256 = 2,213,595,400,050,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 83,794,038,078,300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 721,264,246,243,000,000,000,000,000
이런 거대한 값은 계산기나 컴퓨터에서 오버플로우 오류를 발생시킵니다.
그렇지 않은 경우라도 이런 거대한 숫자의 mod 값을 직접 알아내기 위해서는 오랜 시간 이 걸립니다.

식에 포함된 항의 크기를 줄이고 보다 빠르게 계산하려면 어떻게 해야 할까요?

2^90 mod 13를 계산하고 싶지만 지금 갖고 있는 계산기로는 2^50보다 큰 값을 나타낼 수 없다고 가정합시다.
아래에 간단한 분할 정복(divide and conquer) 전략을 나타냈습니다:
지수 공식을 이용해
나눕니다
2^90 = 2^50 * 2^40
mod C
를 각 항에 적용합니다
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
의 성질을 이용해서
부분을 합칩니다
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

B가 2의 거듭제곱일 때 A^B mod C를 빨리 계산하는 방법

7^10보다 큰 숫자를 나타내지 못하는 계산기를 이용하여 7^256 mod 13를 어떻게 계산할 수 있을까요?
We could split 7^256 into 25 parts of 7^10 and 1 part of 7^6, but this wouldn't be very efficient.
더 좋은 방법이 있습니다....