Joonas' Note

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

알고리즘

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

joonas 2017.10.31 23:17

중국인의 나머지 정리(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) = 4 \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)에서 대표적으로 사용된다.


6 Comments
  • 프로필사진 ㅇㅈㅎ 2017.11.06 22:51 신고 ㅎㅇ
  • 프로필사진 joonas 2017.11.07 09:04 신고 ㅋㅋㅋ누추한 곳에 귀하신분이..
  • 프로필사진 dajinstory 2018.10.12 16:10 신고 좋은 글 감사합니다 :)

    한가지 궁금점이 있습니다.
    중국인의 나머지 정리는, 여러개의 합동식에 대해서, mod 값이 전부 서로 서로소인 경우에만 사용 가능한가요?
  • 프로필사진 joonas 2018.10.13 16:05 신고 댓글 감사합니다 :)

    답변을 드리자면 한가지 예로, \( x \equiv
    1~(mod~6) \) 과 \( x \equiv 1~(mod~9) \) 는 mod값이 서로소는 아니지만 (gcd(6, 9) = 3)
    두 합동식을 만족하는 수 \(x \equiv 37~(mod~54)\) 가 있습니다.
  • 프로필사진 dajinstory 2018.10.23 19:41 신고 음.... 예시라기보다, 일반적인 풀이가 있는지 궁금하네요 ㅠㅜ

    지금 생각하고 있는 바로는

    33 = 5(mod 28) = 33(mod 36)이면
    각각 모듈러 값 a(=28), b(=36)를 a,b의 최대공약수 GCD로 나누어주어 다시표현하여
    x'= 5(mod 7) = 6(mod 9) 로 바꾼다음.
    x'을 우선 구했습니다.

    x' = 9A + 7B

    s t R Q
    1 0 9
    0 1 7 1
    1 -1 2 3
    -3 4 1 2
    - - 0

    9의 mod7 에 대한 곱셈의 역원 = (7-3)%7 = 4
    7의 mod9 에 대한 곱셈의 역원 = 4

    x' = (9*4*5+7*4*6)%(7*9)=33
    이 나옵니다.

    지금 테스트중인 몇가지 경우에 대해선, 전부 바로 나오긴 하지만, 예외케이스가 분명 존재할것 같아서, 저 33값에, GCD값을 더해가며, 가장 작은 값을 구하려 합니다.... 지식이 얕아 감이 잘 잡히지 않네요.... 혹시 관련된 내용 아시는거 있으신가요??
  • 프로필사진 joonas 2018.10.29 17:45 신고 서로소가 아니더라도 \(A_1, A_2\)를 구하는 과정에서 각 모듈러 값이 포함되므로 상관이 없지 않을까요?

    저도 자세히 아는 것이 아니라, 정확하게 답변을 못해드려서 죄송합니다..
댓글쓰기 폼