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

한 줄 정의: 서로 다른 수로 나눈 나머지 조건 여러 개를 동시에 만족하는 수가 정해진 범위 안에서 딱 하나로 결정된다는 정리입니다.

쉽게 풀면

"3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는 무엇일까?"라는 퍼즐을 떠올려 보세요. 조건이 하나뿐이면 답이 무수히 많지만, 서로소인 나머지 조건 여러 개를 동시에 걸면 일정한 범위(여기서는 3×5×7=105 이내) 안에서 답이 딱 하나로 좁혀집니다. 이것이 중국인의 나머지 정리입니다.

이름은 고대 중국의 산학서에서 비슷한 문제가 처음 등장한 데서 유래했으며, 여러 조건을 짜맞춰 하나의 답을 복원하는 방식이라는 점에서 퍼즐 조각을 맞추는 것과 비슷합니다.

왜 중요한가

이 정리는 큰 수 하나를 다루는 대신 여러 개의 작은 수로 쪼개 독립적으로 계산할 수 있게 해주므로, 계산 복잡도를 줄이거나 연산을 병렬화해야 하는 분야에서 핵심 도구로 쓰입니다.

특히 암호학에서는 RSA 개인키 연산을 가속하는 표준적인 방법으로 자리 잡았고, 신호 처리나 분산 시스템에서도 큰 값을 작은 조각으로 나눠 다루는 여러 기법의 이론적 토대가 됩니다. 이런 이유로 정수론을 다루는 논문뿐 아니라 암호학, 코딩이론, 분산 컴퓨팅 논문에서도 폭넓게 인용됩니다.

핵심 정리

서로 소인 법 m₁, m₂, …, m_k가 있을 때, 연립 합동식 x ≡ a₁ (mod m₁), …, x ≡ a_k (mod m_k)는 0 ≤ x < M = m₁·m₂·…·m_k 범위에서 해가 정확히 하나이고, 모든 해는 M을 법으로 합동입니다.
구성 방법: M_i = M/m_i로 두고 y_i를 M_i·y_i ≡ 1 (mod m_i)인 수(역원)로 잡으면, x = Σ a_i·M_i·y_i (mod M)이 해입니다.
“서로 소”가 조건입니다. 법이 서로 소가 아니면 해가 없을 수 있습니다. 일반화하면 두 합동식은 a₁ ≡ a₂ (mod gcd(m₁, m₂))일 때에만 해가 존재하고, 해는 lcm(m₁, m₂)를 법으로 유일합니다.
큰 수의 계산을 작은 법의 계산 여러 개로 쪼갰다가 합치는 도구로 암호학(RSA의 복호화 가속), 컴퓨터 대수, 오류 정정 부호에서 쓰입니다.
이름은 고대 중국 수학서 『손자산경』의 “물건 수 세기” 문제에서 왔습니다.

예시로 보기

가상의 예입니다(코드로 계산). “3으로 나누면 2, 5로 나누면 3, 7로 나누면 2가 남는 수”를 찾습니다. M = 3×5×7 = 105입니다.

법 3: a = 2, M_i = 35, M_i의 역원 y = 2 (35×2 mod 3 = 1)
법 5: a = 3, M_i = 21, M_i의 역원 y = 1 (21×1 mod 5 = 1)
법 7: a = 2, M_i = 15, M_i의 역원 y = 1 (15×1 mod 7 = 1)

x = 2×35×2 + 3×21×1 + 2×15×1 = 233 ≡ 23 (mod 105). 0 이상 105 미만에서 조건을 모두 만족하는 수를 전수 조사해 보면 23 하나뿐이어서 같은 결과입니다. 이 수에 105의 배수를 더한 수(128, 233, …)도 모두 해입니다.

자주 하는 오해

오해	바로잡기
해가 반드시 있고 유일하다.	법이 서로 소일 때 M 범위에서 유일합니다. 서로 소가 아니면 해가 없거나(양립 불가), 있어도 법이 lcm으로 바뀝니다.
해는 하나뿐이다.	M 범위 안에서 하나일 뿐, M의 배수만큼 더한 무한히 많은 정수가 해입니다.
a_i를 그냥 더하면 된다.	M_i와 역원 y_i를 곱해야 합니다. 그래야 다른 법에서는 0이 되고 자기 법에서만 a_i가 남습니다.
컴퓨터 암호학에서만 쓰인다.	정수론의 구조 정리로서 환론(Z/MZ ≅ Z/m₁Z × … × Z/m_kZ)에서도 기본입니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

"큰 정수 하나를 서로소인 여러 개의 작은 모듈러스로 분할하여 병렬 연산을 수행한 뒤, 중국인의 나머지 정리(Chinese Remainder Theorem)로 원래 값을 복원하였다."

이 문장은 계산량이 큰 정수 연산을 작은 단위 여러 개로 쪼개 동시에 처리한 다음, 이 정리를 이용해 원래의 큰 수로 다시 합쳤다는 뜻입니다. 암호학(RSA 복호화 가속), 오류 정정 부호, 병렬 계산 최적화 논문에서 자주 활용됩니다.

"제안하는 비밀 분산(secret sharing) 기법은 중국인의 나머지 정리(Chinese Remainder Theorem)에 기반하여, 각 참여자에게 서로 다른 모듈러스에 대한 나머지 값을 분배함으로써 임계값 이상의 참여자가 모여야만 원래 비밀을 복원할 수 있도록 설계되었다."

이 문장은 정보보안 분야의 비밀 분산 기법이 이 정리를 어떻게 활용하는지 보여줍니다. 비밀 값을 여러 조각의 나머지 정보로 나눠 각 참여자에게 분배하고, 충분한 수의 조각이 모였을 때만 원래 값을 복원할 수 있도록 설계하는 데 이 정리가 쓰입니다.

"센서 배열에서 수집된 신호의 주파수를 여러 서로소 표본율로 각각 낮게 샘플링한 뒤, 중국인의 나머지 정리(Chinese Remainder Theorem)를 적용해 모호성 없이 원래의 고주파 성분을 복원하였다."

이 문장은 신호 처리 분야의 활용을 보여줍니다. 낮은 표본율 여러 개를 조합해 실제로는 훨씬 높은 주파수를 모호함 없이 알아내는 기법(언더샘플링 기반 주파수 복원)에서도 이 정리의 원리가 응용됩니다.

조금 더 깊게 보면

실제 구현에서는 정리가 성립하는 조건과 복원 알고리즘을 구분해서 볼 필요가 있습니다. 여러 나머지 값으로부터 원래 수를 구체적으로 계산할 때는 각 모듈러스에 대한 모듈러 역원(modular inverse)을 구해 결합하는 방식이 흔히 쓰이며, 이 과정에서 유클리드 호제법이 함께 사용됩니다.

또한 암호학이나 부호이론에서는 이 정리를 정수 집합뿐 아니라 다항식 링(ring) 등 더 일반적인 대수 구조로 확장한 버전을 다루기도 하는데, 이런 일반화된 형태를 논문에서 만나면 기본적인 정수론적 CRT와 같은 발상이 더 넓은 구조에 적용된 것으로 이해하면 됩니다.

주의할 점

이 정리가 유일한 해를 보장하려면 나누는 수들이 서로소여야 합니다. 나누는 수들이 공약수를 가지면 조건에 따라 해가 아예 없거나, 하나로 정해지지 않을 수 있어 모듈러 연산의 기본 전제부터 다시 확인해야 합니다.

헷갈리기 쉬운 용어

나머지 계산에 관한 용어와 혼동되기 쉽습니다.

용어	한 줄 설명
모듈러 산술	나머지만으로 하는 계산, 합동식의 바탕
중국인의 나머지 정리	여러 합동식을 동시에 만족하는 수가 있고 유일함을 보장하는 정리
오일러 정리/페르마 소정리	a<sup>φ(n)</sup> ≡ 1 (mod n) 꼴로 거듭제곱의 나머지를 다루는 정리(별개)

참고 문헌

Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.
Ireland, K., & Rosen, M. (1990). A Classical Introduction to Modern Number Theory (2nd ed.). Springer.
Hardy, G. H., & Wright, E. M. (1938). An Introduction to the Theory of Numbers. Oxford University Press.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.