모듈러 산술(Modular Arithmetic), 나머지 연산

1. 모듈러 연산(Modular arithmetic)

모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법
나머지를 이용한 연산으로 나머지 연산이라고도 불립니다.

다양한 암호 시스템에서 계산 결과가 항상 0 ~ (m-1) 범위에있는 경우 모듈러 연산을 사용하는데

이때 m은 %를 하고자 하는 modular 값을 말합니다.

a mod b : a를 b로 나눈 나머지

17 mod 5 = 2
7 mod 11 = 7
20 mod 3 = 2
11 mod 11 = 0

음수의 경우에도 모듈러 연산이 가능하다.

-3 mod 11 = 8
-1 mod 11 = 10
25 mod 5 = 0
-11 mod 11 = 0

음수를 mod 할 경우에는 양수라 생각하고 mod를 한 후 + m을 해주면 됩니다.

예를 들어 -45 mod 11이면 45 mod 11 = 1 에서 -1 + 11 = 9와 같습니다.

합동 (Congruent)

• (a mod n) = (b mod n), 두 정수 a와 b는 modulo n에 대해 합동
• a ≡ b mod n 으로 표기
• ex) 16와 23은 mod 7 에 대하여 합동

모듈러 연산자 특성

1)

• [(a mod n)+(b mod n)] mod n = (a+b) mod n

• [(a mod n)*(b mod n)] mod n = (a*b) mod n

example)

a = 11, b = 15, n = 8

1. (a + b) mod n = ((11 mod 8) + (15 mod 8)) mod 8 = 3 + 7 mod 8

                        = 10 mod 8 = 2

2. (a b) mod n = ((11 mod 8) (15 mod 8)) mod 8 = 3 * 7 mod 8

                        = 21 mod 8 = 5

2) 교환법칙

• (w+x) mod n = (x+w) mod n

• (wx) mod n = (xw) mod n

3) 결합법칙

• [(w+x)+y] mod n = [w+(x+y)] mod n

• [(wx)y] mod n = [w(xy)] mod n

4) 분배법칙

• [w*(x+y)] mod n = [(wx)+(wy)] mod n