[Khan Academy] Modulo Operation

학습 배경

17466번: N! mod P (1)

소수 P에 대해 N! mod P를 구하는 문제이다.

이를 빠르게 계산하려면 곱 연산과 모듈로 연산 간의 관계를 이해할 필요가 있다고 생각했다.

다행히 이를 배울 수 있도록 친절하게 구성된 사이트가 있었다.

 

학습

---

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

연산의 정의

나머지 정리: 피제수가 양수/음수인 경우

A, B	A = B * Q + R	A % B
5, 3	5 = 3 * 1 +2	5 % 3 = +2
-5, 3	-5 = 3 * -2 +1	-5 % 3 = +1

 

---

합동과 모듈 (개념 이해하기) | 모듈로 연산 | Khan Academy

연산에 대한 합동

정수 k, n, m에 대해 A =  n * C + k, B =  m * C + k이면,

A, B는 mod C에 대해 합동 관계이다.

이와 같은 관계를 정리한 동치식의 종류와 그 성질은 다음과 같다.

동치식

동치의 성질: 반사성, 대칭성, 추이성

---

모듈로 덧셈과 뺄셈 (개념 이해하기) | 암호학이란? | Khan Academy

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

모듈로 곱셈 전 덧셈/뺄셈에 대한 성질부터 공부한다.

학습 링크에 정의가 있지만 개인적으로도 증명을 시도해보았다.

증명

(A+B) mod C 정리

나머지 정리에 의해 k*C 꼴의 항은 mod C 결과에 고려되지 않아 생략할 수 있다.
m_a + m_b에 대해 다시 나머지 정리를 적용하면

m_c = (m_a + m_b) mod C 이고,

　m_a = A mod C,

　m_b = B mod C,

　m_a + m_b = (A + B) mod C이므로,

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

　　 = ((A + B) mod C) mod C가 된다.

뺄셈도 덧셈과 동일한 성질을 갖는다.

---

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

모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | Khan Academy

모듈로 곱셈

모듈로 거듭제곱

결과적으로 문제 풀이에 적용하는 것이 목적이기 때문에 증명 과정은 생략하도록 한다.

---

빠른 모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | Khan Academy

빠른 모듈로 거듭제곱법

아이디어가 재밌어서 가져왔다.

1. A^B 거듭제곱을 곱으로 분해한다.
2. 이 때, 기존 공식처럼 A*A*...*A 로 모두 나누지 않는 것이 포인트
3. A^k를 구하기 위해 A^k/2를 구하는 식으로 dynamic programming 기법을 사용한다.

---

마치며...

다양한 공식은 습득했지만, 이것을 팩토리얼에 적절하게 적용하는 방식은 고민을 좀 더 해봐야 할 것 같다.