Modulo 연산.

Presentation on theme: "Modulo 연산."— Presentation transcript:

1 Modulo 연산

2 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

3 “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

4 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

5 정리 ((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은 서로 소)

6 Modular 덧셈 예 3 + 5 = 2 mod 6 2 + 4 = 0 mod 6 3 + 3 = 0 mod 6

7 Modular 곱셈 예 3  4 = 0 mod 6 2  4 = 2 mod 6 5  5 = 1 mod 6

8 Modular 역(Inverse) -x mod n : x mod n의 덧셈 역 x-1 mod n : x mod n의 곱셈 역
-2 mod 6 = 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이 “서로 소”일 때 만 존재

9 지수 연산 => 곱셈의 반복으로 수행가능
예) 117 mod 13 112 = 121 = 4 mod 13 114 = 42 = 3 mod 13 117 = 11*4*3 = 2 mod 13