[정보보안] 모듈로 계산의 성질 (modular)

(A * B) mod C = (A mod C * B mod C) mod C

 

A^B mod C의 경우에는 위 성질을 이용해도 되지만, 빠른 모듈로 거듭제곱법을 이용하면 훨씬 빠르게 풀 수 있다.

 

출처: https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

 

임의의 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^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^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^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^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^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

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