중국인의 나머지 정리 - 이해하기 쉬운 설명

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

연립 합동식의 유일한 해를 찾는 정리이다.

예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때만 생각해보자.

$$\begin{cases} x \equiv 3 ~ (mod~ 5)~\dashrightarrow~ (a) \\ x \equiv 4~ (mod~ 7)~\dashrightarrow ~(b)  \end{cases}$$

위 두 합동식 (a), (b)를 모두 만족하는 어떤 정수 $x$는 어떻게 찾을 수 있을까?

어떤 수 $x$는 위 두 합동식을 모두 만족하기 위해 (a), (b)의 해를 각각 $A_1$, $A_2$라고 하면 아래의 형태가 된다.

$$x \equiv A_1 + A_2 ~ (mod ~ 5 \cdot 7)$$

식 (a)를 만족하기 위해 $A_1$는 5로는 나누어 떨어지지 않아야 한다 (나머지가 남아야하니까) 즉, mod 5*7=35 에서 5를 제외한 나머지 수들의 곱을 포함한 수이다. 마찬가지로 $A_2$는 7로 나누어 떨어지지 않는 수이므로 식은 아래과 같이 적을 수 있다.

$$x \equiv 7a_1 + 5a_2 ~ (mod ~ 5 \cdot 7)$$

위 식을 이용해서 다시 전개해보면 두 합동식을 모두 만족함을 알 수 있다.

$$\begin{cases} x \equiv 7a_1 + 5a_2 ~(mod ~ 5) \equiv 7a_1 + 0 ~(mod~ 5) \equiv A_1 \\ x \equiv 7a_1 + 5a_2~ (mod ~ 7) \equiv 0 + 5a_2~ (mod~ 7) \equiv A_2 \end{cases}$$

그럼 이제 문제는 $7a_1 \equiv 3$, $5a_2 \equiv 4$를 만족시키는 $a_1$, $a_2$를 찾아야한다.

모듈러 연산만 아니라면 수를 이항시켜서 바로 구할 수 있는데, 모듈러 연산에서는 그리 쉽지 않다.
모듈러 연산에서 곱셈의 역원을 찾기 위해 확장 유클리드 알고리즘이 필요하다. (작은 수는 직접 찾을 수 있음)

곱셈의 역원은 페르마의 소정리나 확장 유클리드 알고리즘으로 구할 수 있는데, 이 글에 다루기엔 너무 긴 내용이므로 생략한다.

$a$에 곱해져서 1로 만드는 수를 곱셈의 역원 $a^{-1}$로 표기한다. 작은 수로 간단한 예시를 들면, 아래의 식을 만족하면 된다.

$$\text{if}~~a = 2~(mod~3),~~~ a \cdot a^{-1} \equiv 1~(mod~3)$$

mod 3 에서 가능한 $a^{-1}$는 많지만, 그 중 하나인 $2^3 = 8$로 정해본다면,

$$a \cdot a^{-1} \equiv 2 \cdot 8 = 16 \equiv 1~(mod~3)$$

을 만족하는 것을 알 수 있다.

각 합동식을 만족하는 $a_1$, $a_2$는 역원을 이용해서 아래처럼 전개하면 구할 수 있다.

$$\begin{cases} 7a_1 \equiv 7 \cdot (7^{-1} \cdot 3) \equiv 3~(mod~5) \\ 5a_2 \equiv 5 \cdot (5^{-1} \cdot 4) \equiv 4~(mod~7) \end{cases}$$

$$\begin{cases} 7a_1 = 7 \cdot (7^{-1} (mod~5) \cdot 3) = 7 \cdot (\color{red}{3} \cdot 3) = 63 \\ 5a_2 = 5 \cdot (5^{-1} (mod~7) \cdot 4) = 5 \cdot (\color{red}{10} \cdot 4) = 200 \end{cases}$$

$7^{-1}~(mod~5)$ 는 5가 소수이고 5와 7이 서로소이므로, 페르마의 소정리에 의해 구할 수 있다.

페르마의 소정리를 이용하면 $7^{-1} \equiv 7^{5-2} \equiv 7^3 = 343 \equiv 3~(mod~5)$

$$x = A_1 + A_2 = 7a_1 + 5a_2 = 63 + 200 = 263 \equiv 18~(mod~35)$$

원하던 $x$를 구했다. 두 합동식에 $x = 18$을 대입해보면 신기하게도 모두 만족한다.

그럼 합동식 3개도 해보자.

중국인의 나머지 정리는 원래 여러 개의 합동식을 만족하는 유일한 해를 찾는 정리이다. 전개 방식은 똑같으니까 빠르게 찾아보자.

$$\begin{cases} x \equiv \color{blue}{1}~(mod~3) \\ x \equiv \color{blue}{2}~(mod~5) \\ x \equiv \color{blue}{3}~(mod~7) \\ \end{cases}$$

$$\begin{align} x & \equiv A_1 + A_2 + A_3~(mod~3 \cdot 5 \cdot 7)\\ & = (5 \cdot 7)a_1 + (3 \cdot 7)a_2 + (3 \cdot 5)a_3\\ & = 35a_1 + 21a_2 + 15a_3\\ & = 35 \cdot \color{red}{2} \cdot \color{blue}{1} + 21 \cdot \color{red}{1} \cdot \color{blue}{2} + 15 \cdot \color{red}{1} \cdot \color{blue}{3}\\ \end{align}$$

$$\therefore x = 157 \equiv 52~(mod~105)$$

검산까지 해보면 모두 만족하는 것을 알 수 있다.

이걸 어디에?

RSA 알고리즘에서 복호화(Decryption)에서 대표적으로 사용된다.