모듈러 연산(Modular Arithmetic)

​모듈러 연산은 간단히 말하자면 나머지를 이용한 계산식이지만 여러 성질들이 있어 잘 사용하면 큰 수에 대한 연산 시 수고를 덜어준다.

다음은 모듈러 연산에 대한 증명 방법이다.

 

1. (A+B) % C = (A%C + B%C) % C

 

A mod C = a

B mod C = b

라고 하자.

 

A = a + iC

B = b + jC

 

(A+B) % C

= (a+b+(i+j)C) % C

= (a+b) % C

= (A mod C + B mod C) % C

 

2. (A-B) % C = (A%C - B%C) % C (1.과 같은 방식으로 증명 가능)

 

3. (A*B) % C = ((A%C) * (B%C)) % C

 

A mod C = a

B mod C = b

라고 하자.

 

A = a + iC

B = b + jC

 

(A*B) % C

= (ab + biC + ajC + ij*C^2) % C

= (ab) % C

= ((A mod C)*(B mod C)) % C

 

특히 3.과 같은 곱셈이 여러 개로 이루어진 식(가장 대표적으론 지수 형태의 수 ex)11^9)에서 분할 정복을 통해 접근할 수 있다.

11^9 mod 3

= 11^4 mod 3 * 11^4 mod 3 * 11 mod 3

= 11^2 mod 3 * 11^2 mod 3 * 11^2 mod 3 * 11^2 mod 3 * 11 mod 3

...

 

이런 식으로 2진법으로 쪼개나가는 방법을 이용할 수 있어서 계산의 편의성이 증가한다.

 

이와 더불어, 모듈러의 나눗셈 또한 존재하는데

이때는 분모의 역원을 구하고 그 값을 이용해서 식을 작성하면 된다.

ex)

 

- (7/10) mod 13을 구하고자 할 때,

 

10*4 mod 13 = 1 이므로

 

(7/10) mod 13

= (10*4 mod 13) * ((7/10) mod 13)

= 4*7 mod 13

= 2 mod 13

 

3번 곱셈의 모듈러 연산을 활용하여 구해낼 수 있다.