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

쌍마다 서로소인 여러 수로 나눈 나머지를 모아 두면, 그것만으로 원래 수가 하나의 합동류로 정해진다. 중국인의 나머지 정리는 그런 수가 반드시 존재하고 그 합동류가 유일하다는 것을 보장하고, 그 수를 직접 만드는 방법까지 준다.

정확한 설정

$m_1, \ldots, m_r$이 쌍으로 서로소(pairwise coprime): 임의의 $i \neq j$에 대해 $\gcd(m_i, m_j) = 1$.

여기서 주의할 점은 전체 gcd가 1인 것 과 쌍으로 서로소 는 다르다는 것이다. 예를 들어 $\{6, 10, 15\}$는 $\gcd(6,10,15)=1$이지만, $\gcd(6,10)=2 \neq 1$이므로 쌍으로 서로소가 아니다.

$m = m_1 \cdot m_2 \cdots m_r$로 정의한다.

정리: 임의의 정수 $c_1, \ldots, c_r$에 대해, 다음 연립 합동식을 동시에 만족하는 $x$가 $\bmod\ m$에서 유일하게 존재한다.

$$x \equiv c_1 \pmod{m_1}, \quad x \equiv c_2 \pmod{m_2}, \quad \ldots, \quad x \equiv c_r \pmod{m_r}$$

유일성 증명

$x$와 $y$가 모두 연립 합동식을 만족한다고 하자. 그러면 각 $i$에 대해

$$x \equiv c_i \pmod{m_i}, \quad y \equiv c_i \pmod{m_i} \implies m_i \mid (x - y)$$

$m_1, \ldots, m_r$이 쌍으로 서로소이고 모두 $(x-y)$를 나누므로, 이들의 곱도 $(x-y)$를 나눈다.

$$m = m_1 \cdots m_r \mid (x - y) \implies x \equiv y \pmod{m}$$

따라서 해는 $\bmod\ m$에서 유일하다.

존재성 증명 — 구성 (Construction)

다음과 같이 변수를 정의한다.

$$M_i = \frac{m}{m_i} \quad \text{($m_i$를 제외한 나머지를 모두 곱한 값)}$$

$M_i$와 $m_i$는 서로소이다 ($m_i$를 제외한 나머지의 곱이므로). 따라서 $M_i$의 $\bmod\ m_i$ 역원이 존재한다.

$$N_i = M_i^{-1} \pmod{m_i} \quad \text{(베주 항등식으로 계산)}$$

이제 다음을 해(解)로 정의한다.

$$x = \sum_{i=1}^{r} c_i M_i N_i \pmod{m}$$

검증: $j$번째 조건 $x \equiv c_j \pmod{m_j}$를 확인한다.

$$x \bmod m_j = \sum_{i=1}^{r} c_i M_i N_i \bmod m_j$$

• $i \neq j$인 항: $M_i = m/m_i$에 $m_j$가 인수로 포함되어 있으므로 $M_i \equiv 0 \pmod{m_j}$. 해당 항은 사라진다.
• $i = j$인 항: $M_j N_j \equiv 1 \pmod{m_j}$ (역원의 정의). 따라서 $c_j M_j N_j \equiv c_j \pmod{m_j}$.

$$x \equiv c_j \pmod{m_j} \quad \checkmark$$

단계별 계산 예시

연립 합동식: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$

$m = 3 \times 5 \times 7 = 105$

단계 1 — $M_i$ 계산:

$$M_1 = \frac{105}{3} = 35, \quad M_2 = \frac{105}{5} = 21, \quad M_3 = \frac{105}{7} = 15$$

단계 2 — $N_i$ 계산 (베주 항등식 또는 직접 탐색):

$$35 \equiv 2 \pmod{3} \implies N_1 = 2^{-1} \pmod{3} = 2 \quad (2 \times 2 = 4 \equiv 1)$$ $$21 \equiv 1 \pmod{5} \implies N_2 = 1^{-1} \pmod{5} = 1$$ $$15 \equiv 1 \pmod{7} \implies N_3 = 1^{-1} \pmod{7} = 1$$

단계 3 — 합산:

$$x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233$$ $$233 \bmod 105 = 23$$

검증: $23 = 7 \times 3 + 2$ ✓, $23 = 4 \times 5 + 3$ ✓, $23 = 3 \times 7 + 2$ ✓

연산 보존 성질

$x$가 $(c_1, \ldots, c_r)$에, $y$가 $(d_1, \ldots, d_r)$에 대응할 때, CRT 표현에서의 연산이 원래 연산을 보존한다.

$$x + y \longleftrightarrow (c_1 + d_1,\ c_2 + d_2,\ \ldots,\ c_r + d_r)$$ $$x \cdot y \longleftrightarrow (c_1 d_1,\ c_2 d_2,\ \ldots,\ c_r d_r)$$

즉, $m$에 대한 큰 연산을 $m_i$들에 대한 작은 연산들로 분해 할 수 있고, 결과를 다시 합칠 수 있다. 이것이 CRT 최적화의 핵심이다.

응용 — RSA-CRT 최적화

RSA 복호화는 $m = c^d \bmod n$ ($n = pq$)을 계산하는데, $d$가 수백 비트이면 비용이 크다.

RSA-CRT 방법: $n = pq$ ($p$, $q$ 소수, $\gcd(p,q)=1$)일 때 CRT를 적용한다.

$$m_p = c^{d_p} \pmod{p}, \quad d_p = d \bmod (p-1) \quad \text{(페르마의 소정리 적용)}$$ $$m_q = c^{d_q} \pmod{q}, \quad d_q = d \bmod (q-1)$$

$m_p$와 $m_q$를 구한 뒤 CRT로 $m \bmod n$을 복원한다.

속도 향상 이유. 비용을 세려면 모형을 먼저 정해야 한다. 모듈러스가 $\ell$비트일 때 교과서 곱셈으로 모듈러 곱셈 한 번이 $O(\ell^2)$이고, 제곱·곱셈 방식은 지수의 비트 수만큼 곱셈을 돌린다. 지수도 $\ell$비트면 지수 연산 한 번은 $O(\ell^3)$이다.

RSA-CRT에서는 두 가지가 함께 반으로 줄어든다. 모듈러스가 $n$에서 $p$, $q$로 바뀌어 $\ell/2$비트가 되고, 지수도 $d$에서 d_p = d mod (p-1)로 바뀌어 $\ell/2$비트가 된다. 그래서 한 번의 비용이

\left(rac{\ell}{2} ight)^3 = rac{\ell^3}{8}

로 떨어진다. 이것을 두 번 하므로 합이 $\ell^3/4$, 곧 원래의 $1/4$이다. 약 4배 가속은 여기서 나온다.

지수가 짧아지는 부분을 빼먹으면 각각 $1/4$에 두 번이라 $1/2$, 곧 2배밖에 되지 않는다. 두 몫이 함께 줄어드는 것이 핵심이다.

CRT로 다시 합치는 비용은 $O(\ell^2)$ 수준이라 $\ell^3$ 앞에서 묻힌다. 다만 이 4배는 교과서 곱셈을 전제로 한 값이다. 곱셈에 더 빠른 알고리즘을 쓰면 지수가 달라져 배수도 달라진다.