핵심 인사이트
- 중국인의 나머지 정리(CRT, Chinese Remainder Theorem)는 서로 소(Coprime)인 여러 모듈로에 대한 나머지가 주어질 때, 원래 수를 고유하게 복원하는 정수론의 핵심 정리 — "x ≡ r1 (mod m1), x ≡ r2 (mod m2) ..." 연립 합동식의 유일 해를 구한다.
- CRT의 핵심 조건은 모듈러들이 쌍으로 서로 소(Pairwise Coprime) — m1, m2, ..., mk가 쌍으로 서로 소이면, 모든 합동식을 동시에 만족하는 x가 [0, M) (M=m1×m2×...×mk) 범위에서 유일하게 존재한다.
- CRT는 RSA 복호화 최적화(CRT-RSA)와 대형 수 계산 분산화에 실용적 — RSA 복호화를 두 개의 작은 소수 기반 연산으로 분리하면 약 4배 속도를 달성하며, 이것이 OpenSSL의 기본 구현이다.
Ⅰ. CRT 정의
중국인의 나머지 정리 (Chinese Remainder Theorem):
연립 합동식:
x ≡ r1 (mod m1)
x ≡ r2 (mod m2)
...
x ≡ rk (mod mk)
조건:
m1, m2, ..., mk: 쌍으로 서로 소 (Pairwise Coprime)
gcd(mi, mj) = 1 (i ≠ j)
정리:
조건 만족 시, 위 연립 합동식은
[0, M) 범위 (M = m1 × m2 × ... × mk)에서
유일한 해 x를 갖는다
역사:
중국 수학자 孫子 (Sun Zi, 3~5세기)
"今有物不知其數, 三三數之剩二, 五五數之剩三, 七七數之剩二, 問物幾何?"
(물건 수: 3으로 나누면 2남, 5로 나누면 3남, 7로 나누면 2남)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
해: x = 23 (최소 양의 해)
직관:
각 모듈러는 서로 다른 "척도"
→ 척도가 독립이면 조합으로 원래 값 복원 가능
마치 여러 눈금 단위로 측정 → 원래 값 결정
📢 섹션 요약 비유: CRT = 여러 단서로 원본 복원 — "3으로 나누면 2 남음, 5로 나누면 3 남음, 7로 나누면 2 남음". 각 단서(나머지)로 원본 수(23) 복원. 단서들이 독립적(서로 소)이어야!
Ⅱ. CRT 알고리즘
CRT 해 구성 알고리즘:
입력:
합동식: x ≡ ri (mod mi), i=1..k
조건: gcd(mi, mj) = 1 (모든 i≠j)
절차:
1. M = m1 × m2 × ... × mk
2. Mi = M / mi (각 i에 대해)
3. yi = Mi^(-1) mod mi
(Mi의 mod mi 역원 = 모듈러 역원)
4. x = Σ(ri × Mi × yi) mod M
예제: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
M = 3 × 5 × 7 = 105
M1 = 105/3 = 35, y1 = 35^(-1) mod 3 = 2^(-1) mod 3 = 2
M2 = 105/5 = 21, y2 = 21^(-1) mod 5 = 1^(-1) mod 5 = 1
M3 = 105/7 = 15, y3 = 15^(-1) mod 7 = 1^(-1) mod 7 = 1
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105
= (140 + 63 + 30) mod 105
= 233 mod 105 = 23
Python 구현:
def crt(remainders, moduli):
M = 1
for m in moduli:
M *= m
result = 0
for r, m in zip(remainders, moduli):
Mi = M // m
yi = pow(Mi, -1, m) # 모듈러 역원 (Python 3.8+)
result += r * Mi * yi
return result % M
# 예제
print(crt([2, 3, 2], [3, 5, 7])) # 23
📢 섹션 요약 비유: CRT 알고리즘 = 퍼즐 조각 맞추기 — 각 모듈러(퍼즐 영역)에서 나머지(조각 힌트)를 모아 전체 그림(원래 수) 복원. M(전체 판), Mi(해당 영역 제외), yi(가중치) 계산!
Ⅲ. CRT 응용
응용 1 - CRT-RSA (빠른 복호화):
RSA 복호화:
M = C^d mod n (n = p × q)
d가 크면 매우 느림 (d: 수백~수천 비트)
CRT-RSA:
대신 두 개의 작은 연산:
dp = d mod (p-1)
dq = d mod (q-1)
Mp = C^dp mod p ← 작은 p로 계산 (빠름)
Mq = C^dq mod q ← 작은 q로 계산 (빠름)
CRT로 합성:
M = CRT(Mp, Mq, p, q)
속도: 약 4배 향상 (직접 계산 대비)
→ OpenSSL 기본 구현 방식
응용 2 - 대형 수 연산:
큰 수 × 큰 수 → 여러 작은 모듈러에서 계산 후 CRT로 복원
병렬 처리 가능:
M mod m1, M mod m2, M mod m3 → 각각 병렬 계산
→ CRT로 M 복원
응용 3 - 코딩테스트:
"N mod 1000000007"과 "N mod 998244353" 동시 만족
→ CRT로 원래 N의 범위 추론
응용 4 - 비밀 공유 (Secret Sharing):
비밀 S를 여러 모듈러로 쪼개 저장
k명 이상 모이면 CRT로 복원
(Threshold Secret Sharing의 기초)
📢 섹션 요약 비유: CRT-RSA = 계산 분업 — RSA 복호화를 p 팀과 q 팀이 나눠 계산(병렬). CRT로 합산. 혼자 계산보다 4배 빠름. OpenSSL도 이 방법 사용!
Ⅳ. 서로 소 조건과 실패 사례
서로 소 조건 중요성:
gcd(mi, mj) ≠ 1이면 CRT 실패 또는 불완전:
예:
x ≡ 1 (mod 4)
x ≡ 3 (mod 6) ← gcd(4,6) = 2 (서로 소 아님!)
x ≡ 1 (mod 4): x = 1, 5, 9, 13, ...
x ≡ 3 (mod 6): x = 3, 9, 15, 21, ...
공통 해: x = 9 (가능)
그러나 M = 4 × 6 = 24 범위에서 유일 해 없을 수 있음
(또는 해가 없을 수 있음: x ≡ 1 mod 4, x ≡ 2 mod 6 → 해 없음)
해결:
모듈러를 소수 거듭제곱으로 분해:
mod 4 = mod 2^2
mod 6 = mod 2 × mod 3
→ 소수 기반으로 변환 후 CRT 적용
일반화 CRT (가필드 정리):
서로 소가 아니어도 적용 가능
gcd(m1, m2) | (r1 - r2) 이면 해 존재
해가 있으면 mod lcm(m1, m2)로 유일
실용적 확인:
프로그래밍 시 모듈러가 서로 소인지 먼저 확인
for i in range(len(moduli)):
for j in range(i+1, len(moduli)):
if gcd(moduli[i], moduli[j]) != 1:
# 서로 소 아님 → 주의 필요
📢 섹션 요약 비유: 서로 소 조건 = 독립적인 단서 — 서로 소가 아닌 단서는 중복 정보(4의 배수인 것과 6의 배수인 것은 2의 배수 정보가 겹침). 독립 단서여야 정확히 복원 가능!
Ⅴ. 실무 시나리오 — 분산 컴퓨팅 대형 수 계산
암호화 프로토콜에서 대형 수 계산:
배경:
RSA-4096: 4096비트 수 (수십만 자리 정수)
곱셈 연산: 매우 느림
필요: 빠른 대형 수 모듈러 거듭제곱
CRT 기반 병렬 계산:
단계 1 - 소수 기저 선택:
N = 큰 수 (계산할 목표)
p1, p2, p3, p4 = 서로 소인 소수들
M = p1 × p2 × p3 × p4 > N
단계 2 - 모듈러 분해 (병렬):
Thread 1: a = N mod p1
Thread 2: b = N mod p2
Thread 3: c = N mod p3
Thread 4: d = N mod p4
단계 3 - 각 모듈러에서 계산 (병렬):
Thread 1: result1 = a^e mod p1 (작은 수)
Thread 2: result2 = b^e mod p2
Thread 3: result3 = c^e mod p3
Thread 4: result4 = d^e mod p4
단계 4 - CRT 복원:
Final = CRT(result1, result2, result3, result4)
이점:
4096비트 수 → 각 1024비트 수 4개
계산 복잡도: O(N^3) → O((N/4)^3) × 4 = O(N^3/16)
이론적 16배 빠름 + 병렬화
실제 OpenSSL RSA:
void RSA_private_decrypt_crt(rsa, ciphertext, plaintext) {
dp = d % (p-1);
dq = d % (q-1);
qinv = modular_inverse(q, p);
mp = modpow(ciphertext, dp, p); // 작은 p로
mq = modpow(ciphertext, dq, q); // 작은 q로
// CRT 합성
h = qinv * (mp - mq) % p;
plaintext = mq + h * q;
}
📢 섹션 요약 비유: CRT 병렬 계산 = 큰 퍼즐 4팀 분담 — 4096피스 퍼즐을 1팀이 하면 느림. 4팀이 1024피스씩 나눠 동시에. CRT로 4팀 결과 합산 → 이론적 16배 빠름!
📌 관련 개념 맵
중국인의 나머지 정리 (CRT)
+-- 조건: 쌍으로 서로 소
+-- 알고리즘: M, Mi, yi, 합산
+-- 응용
| +-- CRT-RSA (4배 빠른 복호화)
| +-- 대형 수 병렬 계산
| +-- 비밀 공유 (Secret Sharing)
+-- 관련
| +-- 모듈러 역원 (pow(a,-1,m))
| +-- 확장 유클리드 알고리즘
+-- 한계
+-- 서로 소 조건 필수
+-- 일반화 CRT (lcm 기반)
📈 관련 키워드 및 발전 흐름도
[孫子算經 (3~5세기)]
연립 합동식 문제
CRT 기원
|
v
[가우스 (1801)]
수론 정리 (Disquisitiones Arithmeticae)
CRT 수학적 정립
|
v
[RSA 암호화 (1977)]
CRT-RSA 최적화
실용 암호학 적용
|
v
[양자 내성 암호 (2020s)]
격자 기반에도 CRT 응용
NTT (Number Theoretic Transform)
|
v
[현재: Kyber/ML-KEM]
CRT 기반 모듈러 구조
NIST PQC 표준 선정
👶 어린이를 위한 3줄 비유 설명
- CRT = 여러 단서로 원본 복원 — "3으로 나누면 2남, 5로 나누면 3남, 7로 나누면 2남" → 원래 수는 23. 단서들이 독립적이어야!
- CRT-RSA = 계산 분업 — RSA 복호화를 p팀·q팀 나눠 계산. CRT로 합산. 4배 빠름. OpenSSL 기본 방식!
- 서로 소 조건 = 독립 단서 필수 — 겹치는 단서(서로 소 아닌 모듈러)는 정보 중복. 독립적 단서여야 정확히 복원!