중국인의 나머지 정리(CRT) 계산기 — 연립 합동식 풀기
x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)… 형태의 연립 합동식을 중국인의 나머지 정리로 풉니다. 법(모듈러스)들이 서로소인지 자동으로 검증하고, 가장 작은 음이 아닌 해와 일반해를 구합니다.
계산 예시: 손자산경의 「미지수 문제」
중국인의 나머지 정리의 기원으로 여겨지는, 3~5세기경 중국의 수학서 『손자산경』에 나오는 고전적인 문제입니다. 「3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는 무엇인가」라는 질문의 답은 105를 법으로 하여 23입니다.
| 조건1 | x ≡ 2 (mod 3) |
|---|---|
| 조건2 | x ≡ 3 (mod 5) |
| 조건3 | x ≡ 2 (mod 7) |
| 해 | x ≡ 23 (mod 105) |
팁
- 법（nᵢ）들이 서로소가 아니면 오류가 발생합니다. 예를 들어 mod 4와 mod 6은 최대공약수가 2이므로 이 계산기로는 풀 수 없습니다（일반화된 중국인의 나머지 정리가 필요한 경우입니다）。
- 나머지 aᵢ가 법 nᵢ보다 크거나 음수여도 괜찮습니다. 내부적으로 자동으로 mod nᵢ 값으로 정규화한 뒤 계산합니다.
- 합동식은 2개에서 5개까지 추가할 수 있습니다. 세 가지 이상의 주기적 조건을 동시에 만족하는 수를 찾는 「병사의 수 맞히기」와 같은 문제에도 응용할 수 있습니다.
- 결과의 일반해는 x ≡ 해 (mod N) 형태로 표시됩니다. N의 정수배를 더한 어떤 수든 원래의 모든 조건을 만족합니다.
자주 묻는 질문
여담 ― 3세기의 수학서에서 RSA 암호 고속화까지
중국인의 나머지 정리의 기원은 3세기에서 5세기경 성립된 것으로 여겨지는 중국의 수학서 『손자산경(孫子算經)』에 실린 「미지수 문제」로 거슬러 올라갑니다. 「3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 것은 몇 개인가」라는 질문은, 여러 나눗셈의 나머지로부터 원래의 수를 역산한다는 현대 CRT와 본질적으로 같은 발상을 이미 보여주고 있었습니다.
중국인의 나머지 정리가 현대에 가장 실용적으로 쓰이는 사례 중 하나는 RSA 암호의 복호화 처리 고속화입니다. RSA 암호의 복호화는 「큰 수를 비밀키로 거듭제곱한 뒤 법으로 나눈 나머지를 구하는」처리인데, 법으로 쓰이는 합성수 n = p × q（p, q는 큰 소수）를 그대로 쓰는 대신, CRT를 이용해 mod p와 mod q 각각에서 독립적으로 계산한 뒤 결과를 결합하면 이론적으로 최대 4배 가까운 속도 향상을 기대할 수 있습니다. 이를 「CRT-RSA」라고 하며, 많은 암호 라이브러리에 구현되어 있는 최적화 기법입니다.
이 도구가 지원하는 것은 법이 모두 서로소인 「고전적인 중국인의 나머지 정리」입니다. 법이 서로소가 아닌 경우（예: mod 4와 mod 6처럼 공약수를 가지는 경우）에도 조건에 따라 해가 존재할 수 있지만, 그 판정과 계산에는 일반화된 확장 알고리즘이 필요하므로 이 도구의 범위 밖으로 두었습니다.