중국인의 나머지 정리(Chinese Remainder Theorem, CRT)

알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.

중국인의 나머지 정리란?

중국인의 나머지 정리는 다음과 같은 여러 선형 합동식을 만족하는 유일한 해를 구할 수 있게 해주는 강력한 정리이다.

$$x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}$$
합동식들의 $a \equiv b \mod m$의 형태에서, 모든 m들은 서로 서로소 관계여야 한다.

또한 각 합동식에서 x의 계수가 1이 아닌 경우가 있는데, 그런 경우에는 확장된 유클리드 알고리즘(EEA)를 사용해서 곱셈 역원을 구해서 양변에 곱해준 후 CRT를 적용한다.

중국인의 나머지 정리를 이해하기 위해서는 확장 유클리드 알고리즘에 대한 이해가 필요하다. 이전에 다루었던 적이 있으니 참고하자.

2024.09.23 - [BOJ/이론] - Extended Euclidean Algorithm (확장된 유클리드 호제법)

Extended Euclidean Algorithm (확장된 유클리드 호제법)

중국인의 나머지 정리 사용하기

일단 먼저 $x \equiv a \mod p,~  x \equiv b \mod p$일때, $ x \equiv c \mod p\cdot q$의 c값을 구하는 방법에 대해 알아보자.

우선 p,q가 서로소이기 때문에 $p \cdot \alpha + q \cdot \beta = 1$을 만족하는 정수 $\alpha ,\beta$를 구할 수 있고(확장된 유클리드 알고리즘 이용), 다음 식이 성립한다.

$$q \cdot \beta \equiv 1 \mod p \\ p \cdot \alpha \equiv 1 \mod q $$

여기서, $c = a \cdot q \cdot \beta + b \cdot p \cdot \alpha$로 정의하면 $c \equiv a \mod p,~  c \equiv b \mod p$이 성립함을 다음과 같이 확인할 수 있다.

$$ \begin{align*}
c & \equiv a \cdot q \cdot \beta + b \cdot p \cdot \alpha \equiv a \cdot q \cdot \beta \equiv a \cdot (q \cdot \beta) \equiv a \cdot 1 \equiv a \pmod{p} \\

c & \equiv a \cdot q \cdot \beta + b \cdot p \cdot \alpha \equiv b \cdot p \cdot \alpha \equiv b \cdot (p \cdot \alpha) \equiv b \cdot 1 \equiv b \pmod{q}
\end{align*}$$

중국인의 나머지 정리 구현

# n = [5, 11, 17]
# a = [2, 3, 5]

def eea(a, b):
    x,y, u,v = 1,0, 0,1
    while b != 0:
        q, r = a//b, a%b
        m, n = x-u*q, y-v*q
        a,b, x,y, u,v = b,r, u,v, m,n
    gcd = a
    return gcd, x, y

def chinese_remainder_theorem(a_list, n_list):
    N = 1
    for n in n_list:
        N *= n
    x = 0
    for a, n in zip(a_list, n_list):
        Ni = N // n
        gcd, mi, _ = eea(Ni, n)
        
        if gcd != 1:
        	return -1
        
        x += a * mi * Ni
    
    return x%N, N
# print(chinese_remainder_theorem(a,n))

위 함수는 순서대로 n, a 값들이 들어있는 list를 입력으로 받아서 답을 return 해준다. 예시로$x \equiv 2 \pmod{5}, \quad x \equiv 3 \pmod{11}, \quad x \equiv 5 \pmod{17}$의 경우가 들어가있다.