Expression
- n | a: a는 n의 배수이다.
- a mod n: a를 n으로 나누었을 때 나머지 값
- $ a \equiv b\ mod\ n $ : a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다, 모듈로 합동)
- $a \equiv b\ mod\ n $ 이면, a - b는 n의 배수이다. -> $ (a - b)\ mod\ n = 0 $
나머지 연산 법칙
I. 덧셈
(A+B) % M = ((A % M) + (B % M)) % M
II. 뺄셈
(A-B) % M = ((A % M) - (B % M) + M) % M
증명
$ 0 \leq A\%M < M $
$ 0 \leq B\%M < M $ 이므로,
$ -M < (A\%M - B\%M) < 2M $ 이다.
따라서 양쪽에 M을 곱해줘야 0보다 큰 결과가 나온다.
$ 0 < (A\%M - B\%M) + M < 3M $
III. 곱셈
(A*B) % M = ((A % M) * (B % M)) % M
증명
(A * B) mod C = (A mod C * B mod C) mod C
LHS = RHS임을 보이면 됩니다.
LHS = (A * B) mod C
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C ( $ \because A = C*Q1+R1,\ B = C*Q2+R2 $ )
LHS = (C^2 * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LHS = (C * (C * Q1*Q2 + Q1*R2 + Q2*R1) + R1 * R2 ) mod C
C * (C * Q1*Q2 + Q1*R2 + Q2*R1)는 C의 배수이기 때문에 C로 나눴을 때 나머지가 0입니다.
LHS = (R1 * R2) mod C
$A = C * Q1 + R1 \ (0 \leq R1 < C,\ Q1\in Z) \therefore\ A\ mod\ C = R1 $
$B = C * Q2 + R2 \ (0 \leq R2 < C, \ Q2\in Z) \therefore B\ mod\ C = R2 $
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
따라서 RHS = LHS 입니다.
LHS = RHS = (R1 * R2) mod C
IV. 거듭제곱
$ 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,083,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}$보다 큰 값을 나타낼 수 없다고 가정합시다.
분할 정복 전략
$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 $
1. B가 2의 거듭제곱일 때, A^B mod C를 빨리 계산하는 방법
$7^{256}\ mod\ 13 = ?$
모듈러 곱셈 법칙을 이용하면 다음이 성립합니다.
$ 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^1 mod\ 13$을 계산한 결과값을 대입 합니다.
$ 7^2 mod\ 13 = (7 * 7) mod\ 13 = 49 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^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 $
이와 같이 이전 계산값을 다음 식에 대입하는 과정을 계속합니다.
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 $
이렇게 B가 2의 거듭제곱일 때 $ A^B mod\ C $를 빠르게 계산할 수 있습니다.
2. B가 2의 거듭제곱이 아닐 때, $A^B mod\ C$를 빨리 계산하는 방법
$ 5^{117} \ mod\ 19 $
1단계: 이진수를 이용하여 B를 2의 거듭제곱으로 분해합니다.
$ 117 = 1110101_{2} $
맨 오른쪽 bit부터 시작합니다. k는 0부터 시작하고, 각 bit가 1이면 $2^k$ 를 추가하고 0이면 넘어갑니다. (k는 자릿수)
$ 117 = (2^0 + 2^2 + 2^4 + 2^5 + 2^6) $
$ 117 = 1 + 4 + 16 + 32 + 64 $
$ 5^{117} \ mod \ 19 = 5^{1+4+16+32+64} \ mod \ 19 $
$ 5^{117} \ mod \ 19 = (5^1 * 5^4 *5^{16} *5^{32} * 5^{64}) \ mod \ 19 $
2단계: $ B=2^k (k \in N ) $ 의 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 $
V. 나눗셈
나눗셈은 모듈로 연산이 성립하지 않습니다. 하지만 모듈러 역수라는 비스무리한 개념은 있습니다.
또한, 페르마의 소정리를 이용하면 제약 속에서 모듈로 나누기 연산이 가능합니다.
$ (a/b) mod\ p = a * b ^{(p-2)} mod\ p $ 이 때, p는 소수, a와 b는 서로소
페르마의 소정리
p가 소수이고, a이 p와 서로소인 양수일 때,
$ a^{p} mod\ p = a \ (p는 소수) $
양변을 $a^2$로 나누면 $a^{p-2}$이 a의 역수가 된다.
$ (a/b) mod\ p = a * b ^{(p-2)} mod\ p \\ a^{p-1} mod\ p = 1 \\ a^{p-2} mod\ p = \frac{1}{a} $
역수란 ?
어떤 수를 곱했을 때 1을 만드는 수
- $ A * \frac{1}{A} = 1$이므로 $A$의 역수는 $\frac{1}{A}$입니다 (ex. 5의 역수는 1/5).
- 0이 아닌 모든 실수는 역수를 가집니다
- A의 역수에 수를 곱하는 것은 그 수로 A를 나누는 것과 같습니다. (ex. 10/5 = 10* 1/5).
모듈러 역수(modular inverse)란?
모듈러 연산에 나누기 연산은 없지만 모듈러 역수는 있습니다.
- A (mod C) 의 모듈러 역수는 $A^{-1}$입니다
- $ (A * A^{-1}) \equiv 1 (mod\ C) $ 또는 $ (A * A^{-1}) mod\ C = 1 $
- C와 서로소인 수 (C와 공통 소인수가 없는 수) 만 모듈러 역수 (mod C) 를 가집니다
모듈러 역수를 구하는 방법
A (mod C)의 모듈러 역수를 구하는 단순한 방법은 다음과 같습니다.
1단계. 0에서 C-1까지의 B값에 대해 A * B mod C 를 계산합니다
2단계. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값입니다
B mod C 항은 0에서 C-1까지의 정수값만 가질 수 있으므로 더 큰 값을 테스트하지 않아도 됩니다.
예제: A = 3, C = 7
1단계. 0에서 C-1까지의 B값에 대해 A * B mod C를 계산합니다
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ 역수를 찾았습니다!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
2단계. A mod C의 모듈러 역수는 A * B mod C = 1를 만족하는 B값입니다.
5*3 mod 7 = 1이므로 3 mod 7의 역수는 5입니다.
예제: A=2, C=6
1단계. 0에서 C-1까지의 B값에 대해 A * B mod C를 계산합니다.
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
2단계. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값입니다.
어떤 B값도 A * B mod C = 1을 만족시키지 않습니다. 그러므로 A는 모듈러 역수 (mod 6)를 갖지 않습니다. 2는 6과 서로소가 아니기 때문입니다.(두 수는 2라는 인수를 공통으로 가집니다)
A (mod C)의 역수를 알아내는 훨씬 빠른 방법이 있는데 이는 확장된 유클리드 호제법을 다루는 다음 글에서 알아도록 하겠습니다.
왜 모듈러 역수가 필요할까요?
PS에는 거의 사용되지 않지만 암호체계에서 매우 중요하므로 다음 포스트를 이해하기 위해서는 익혀두도록 합시다