Modulo 연산
modulo 정의 modulo 연산은 나누기(division)과 나머지(remainder)에 대한 연산이다. 다음과 같이 정의한다. 2
11 mod 7 = 4, 왜냐하면 11 = 7X1 +4 4 mod 7 = ? 4 = 7 X(-1) + 11 , 따라서 4 mod 7 = 11 -11 mod 7 = ? -11 = 7X(-2) + 3, 따라서 -11 mod 7 = 3 3 mod 7 = ? 3 = 7X2 -11, 따라서 3 mod 7 = -11
Knapsack에서 modulo 연산도 여러가지 연산 규칙이 성립한다. 여기서는 공개키 암호 방식을 공부할 때 나온 것을 이해하기 위한 규칙만 따져 본다. 41-1 mod 491 = 12 왜? 492 = 41 X 12 = 41 X 41-1 mod 491 ⇒ 41-1 mod 491 = 12 (41과 491은 서로 소)
RSA에서 x = x’ mod a 이고 y = y’ mod a ⇒ xy = x’y’ mod a M = Cd mod N = (Me mod N)d mod N = (Med mod N) mod N = Med mod N Med = M(ed 1) + 1 = MMed 1 = MMk(N) = M(M(N))k mod N = M1k mod N = M mod N