주요 내용
빠른 모듈로 거듭제곱법
구글 클래스룸B가 2의 거듭제곱일 때 A^B mod C를 빨리 계산하는 방법
모듈러 곱셈 법칙을 이용하면 다음이 성립합니다.
i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
이 성질을 이용하여 7^256 mod 13를 금방 계산할 수 있습니다.
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
다음 식에서 7^1 mod 13을 계산한 결과값을 대입 합니다.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
다음 식에서 7^2 mod 13을 계산한 결과값을 대입 합니다.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
다음 식에서 7^4 mod 13을 계산한 결과값을 대입 합니다.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
이와 같이 이전 계산값을 다음 식에 대입하는 과정을 계속합니다.
5번 반복하면 다음과 같은 결과가 나옵니다.
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
이와 같이 B가 2의 거듭제곱일 때 A^B mod C를 빠르게 계산할 수 있습니다
그렇지만 B가 2의 거듭제곱이 아닐 때도 모듈러 제곱을 쉽게 계산하는 방법도 있어야 할 겁니다
임의의 B에서 A^B mod C를 빨리 계산하는 방법
1단계: 이진수를 이용하여 B를 2의 거듭제곱으로 분해합니다.
맨 오른쪽 숫자부터 시작합니다. k=0이고 각각의 숫자는 다음과 같이 처리합니다.
- 숫자가 1이면 2^k 를 추가하고 그렇지 않으면 추가하지 않습니다
- K에 이 숫자의 자릿수 1을 추가하고 다음 숫자를 처리하기 위해 왼쪽으로 움직입니다.
2단계: 2 ≤ B 인 거듭제곱의 mod C 를 계산합니다
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
3단계: 계산된 mod C 값을 결합하기 위한 모듈러 곱셈 성질 이용
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
참고:
더 많은 최적화 기법이 있지만 본 글의 범위를 벗어나므로 다루지 않겠습니다. 암호학에서 모듈러 지수화를 다룰 때 B > 1000 bits 인 지수를 이용하는 경우가 많다는 것을 참고하세요.