Algorithm
[Algorithm][WIP] 중국인의 나머지 정리 (Chinese Remainder Theorem)
SweetDev
2021. 11. 10. 14:49
서론
중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 문헌인 『손자산경(孫子算經)』에는 나오는 문제로, 내용은 다음과 같다.
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?
x = r1 (mod n1)
x = r2 (mod n2)
...
x = rk (mod nk) 이고 N = n1 * n2 * ... * nk 라고 하자.
mi는 mi * (N/ni) = 1(mod ni)를 계산해서 구한다.
일반해는 x = m1 (N/n1) + m2 (N/n2) + ... + mk (N/nk) mod N
배경 지식
곱셈의 역원 구하기