Modulo 연산
modulo 연산 정의 modulo 연산은 나누기(division)과 나머지(remainder)에 대한 연산이다. 다음과 같이 정의한다. a, n, r, q ∈ Z (정수의 집합) a mod n = r 혹은 r mod n = a iff ∃q, a = qn + r, 0≤r<n 2
“Clock” 연산 예 7 mod 6 = 1 33 mod 5 = 3 33 mod 6 = 3 51 mod 17 = 0 예 7 mod 6 = 1 33 mod 5 = 3 33 mod 6 = 3 51 mod 17 = 0 17 mod 6 = 5 1 5 arithmetic mod 6 2 4 3
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
정리 ((a mod n) + (b mod n)) mod n = (a + b) mod n a = b mod n ⇔ 0 = (a-b) mod n a = a mod n (a+b) (a+c) mod n ⇔ b c mod n (a*b) (a*c) mod n ⇔ b c mod n (단, a와 n은 서로 소)
Modular 덧셈 예 3 + 5 = 2 mod 6 2 + 4 = 0 mod 6 3 + 3 = 0 mod 6
Modular 곱셈 예 3 4 = 0 mod 6 2 4 = 2 mod 6 5 5 = 1 mod 6
Modular 역(Inverse) -x mod n : x mod n의 덧셈 역 x-1 mod n : x mod n의 곱셈 역 -2 mod 6 = 4, 왜냐하면 2 + 4 = 0 mod 6 x-1 mod n : x mod n의 곱셈 역 1 mod n이 되기 위해서 x에 곱해야 하는 수 3-1 mod 7 = 5, 왜냐하면 3 5 = 1 mod 7 x와 n이 “서로 소”일 때 만 존재
지수 연산 => 곱셈의 반복으로 수행가능 예) 117 mod 13 112 = 121 = 4 mod 13 114 = 42 = 3 mod 13 117 = 11*4*3 = 2 mod 13