Joonas' Note

Joonas' Note

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

알고리즘

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

2017. 10. 31. 23:17 joonas

    중국인의 나머지 정리(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_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} $$

    $$ 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)에서 대표적으로 사용된다.


    Comments