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

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

쉽게 풀면

"3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는 무엇일까?"라는 퍼즐을 떠올려 보세요. 조건이 하나뿐이면 답이 무수히 많지만, 서로소인 나머지 조건 여러 개를 동시에 걸면 일정한 범위(여기서는 3×5×7=105 이내) 안에서 답이 딱 하나로 좁혀집니다. 이것이 중국인의 나머지 정리입니다. 이름은 고대 중국의 산학서에서 비슷한 문제가 처음 등장한 데서 유래했으며, 여러 조건을 짜맞춰 하나의 답을 복원하는 방식이라는 점에서 퍼즐 조각을 맞추는 것과 비슷합니다.

왜 중요한가

이 정리는 큰 수 하나를 다루는 대신 여러 개의 작은 수로 쪼개 독립적으로 계산할 수 있게 해주므로, 계산 복잡도를 줄이거나 연산을 병렬화해야 하는 분야에서 핵심 도구로 쓰입니다. 특히 암호학에서는 RSA 개인키 연산을 가속하는 표준적인 방법으로 자리 잡았고, 신호 처리나 분산 시스템에서도 큰 값을 작은 조각으로 나눠 다루는 여러 기법의 이론적 토대가 됩니다. 이런 이유로 정수론을 다루는 논문뿐 아니라 암호학, 코딩이론, 분산 컴퓨팅 논문에서도 폭넓게 인용됩니다.

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

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

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

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

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

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

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

조금 더 깊게 보면

실제 구현에서는 정리가 성립하는 조건과 복원 알고리즘을 구분해서 볼 필요가 있습니다. 여러 나머지 값으로부터 원래 수를 구체적으로 계산할 때는 각 모듈러스에 대한 모듈러 역원(modular inverse)을 구해 결합하는 방식이 흔히 쓰이며, 이 과정에서 유클리드 호제법이 함께 사용됩니다. 또한 암호학이나 부호이론에서는 이 정리를 정수 집합뿐 아니라 다항식 링(ring) 등 더 일반적인 대수 구조로 확장한 버전을 다루기도 하는데, 이런 일반화된 형태를 논문에서 만나면 기본적인 정수론적 CRT와 같은 발상이 더 넓은 구조에 적용된 것으로 이해하면 됩니다.

주의할 점

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