모듈러 연산( modular, 나머지 )

https://www.acmicpc.net/problem/15829

15829번: Hashing

해당 문제를 풀 때 "모듈러 연산"에 관한 개념을 공부했다.

 

모듈러 연산이란

나머지 연산을 의미한다.

N mod m일 때, 0 ~ (m - 1)의 범위 내에서 결과값이 나온다. 

읽는 방법 " N 모듈러 m "

여기서 m은 modular 값이다.

 

N이 음수라면( 결과값이 음수라면 ), N의 절대값에서 mod한 결과에 m을 더하거나 m을 2, 3배 한 값을 결과값에 더해서 0 ~ (m - 1) 사이의 결과값을 도출하면 된다.

 

모듈러의 관계식

const int k;
int a, b, n;
if ((a mod n) == (b mod n) && (a - b) == k*n)
	a와 b는 모듈러 합동 관계;

위 코드의 두 조건문을 만족하면 두 a, b는 모듈러 합동 관계이다.

$$ a \equiv b\;(mod\:c) $$

$$ b \equiv a\;(mod\:c) $$

여기서 (mod c)는 a와 b에 적용할 연산을 나타낸다.

$$ a \equiv b\;mod\;c $$

위 수식과 헷갈리지 말자

// 이런 관계도 있다
(( N + k*m ) mod m) == (N mod m)

모듈러 연산은 0 ~ (m - 1) 사이의 값을 가진다고 했다. 이는 루프를 돌고 있는 것으로 이해할 수 있다.

mod 12

즉, N mod m은 m번 째마다 같은 위치로 돌아온다.

 

$$ a \equiv b\;(mod\; c)\;\wedge \; b \equiv d\;(mod\:c)\;\: \to  \, a \equiv d\;(mod\:c) $$

이런 관계도 있다2

 

모듈러 연산의 성질

1. 덧셈과 뺄셈 성질

(a + b) mod n == ( (a mod n) + (b mod n) ) mod n
(a - b) mod n == ( (a mod n) - (b mod n) ) mod n

앞서 살펴본 (( N + k*m ) mod m == N mod m) 규칙과 몫-나머지 정리를 토대로 성립되는 덧셈 성질이다.

몫-나머지 정리

A = B * Q + R;  (0 <= R < Q)

// 예제1
A mod 47 = 43;
B mod 47 = 46;
(A + B) mod 47 == 42;

// 예제2
1594 mod 6 
== (1800 mod 6 + (-206 mod 6)) mod 6)
== (1500 mod 6 + 90 mod 6 + 4 mod 6) mod 6

2. 곱셈 성질

(a * b) mod n == ( (a mod n) * (b mod n) ) mod n

덧셈, 뺄셈 성질의 예제를 보면 곱셈 성질도 외우기 편하다.

3. 거듭제곱 성질

$$ a^{b}\, mod\, c\, ==\, ((a\, mod\, b)^{b})\, mod\, c $$

a^b 는 굉장히 큰 값을 갖는다. 오버플로우의 원인이 되기도 한다.

 

분할 정복

오버플로우를 막기 위해 분할 정복 전략을 사용한다.

2^90 mod 13 == ??

1. 2^90 == 2^50 * 2^40;
2. 각 항에 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 == 12;

$$ H = \sum_{i=0}^{l-1}a_{i}r^{i}\, mod\, M $$

백준의 hashing 문제는 이러한 분할 정복을 이용해서 위 수식을 코드로 풀어낸다.

 

 

참고한 사이트

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

모듈로 연산이란? (개념 이해하기) | 암호학이란? | Khan Academy