中国剩余定理：一个定理撑起半个密码学

全文分三层：

1. 通俗理解：韩信点兵
2. 实际用处：密码学里 CRT 出现的五个地方
3. 数学原理：环同构、构造性证明、多项式版本，附手算例子

第一层：通俗理解

1.1 韩信点兵

《孙子算经》（约公元 4 世纪）里的题目：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

答案是 $23$。民间口诀叫"韩信点兵"：士兵三人一排、五人一排、七人一排，只报每次剩几个人，就能推出总人数（在 $105$ 以内唯一）。

1.2 一个数，两种"身份证"

$0$ 到 $14$ 的每个数，都可以用"除以 3 的余数、除以 5 的余数"这一对数来唯一表示：

15 个数，15 种不同的余数对，一一对应。而且更妙的是：加法和乘法可以分开在两边算。比如 $4 \times 7 = 28 \equiv 13 \pmod{15}$；用余数对算：

$$(1, 4) \times (1, 2) = (1 \cdot 1 \bmod 3,\ 4 \cdot 2 \bmod 5) = (1, 3),$$

查表，$(1, 3)$ 对应的正是 $13$。

1.3 为什么这很有用

大数运算的代价随位数增长很快（乘法大约是位数的平方）。把一个 2048 位的数拆成两个 1024 位的余数，每边的乘法便宜 4 倍，而且两边可以并行。这就是"分而治之"。

第二层：实际用处

此外，素性检验里分析 Carmichael 数、Shamir秘密分享的拉格朗日插值，也是 CRT 的同类思想（拉格朗日插值本身就是多项式环上的 CRT）。

第三层：数学原理

3.1 定理

设 $m_1, \dots, m_k$ 两两互素，$M = m_1 \cdots m_k$。则映射

$$\pi: \mathbb{Z}_M \to \mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k},\qquad x \mapsto (x \bmod m_1, \dots, x \bmod m_k)$$

是环同构。

证明思路（抽象代数标准做法）：

1. 先看 $\tilde\pi: \mathbb{Z} \to \prod \mathbb{Z}_{m_i}$，它显然是环同态（每个分量都是取模同态）；
2. 核是"同时被所有 $m_i$ 整除的数"，由两两互素，就是 $M\mathbb{Z}$；
3. 由第一同构定理，$\mathbb{Z}/M\mathbb{Z} \cong \operatorname{im}\tilde\pi$；
4. 两边都有 $M$ 个元素，单射即满射，所以是同构。

更一般的版本：交换环 $R$ 中两两互素（$I_i + I_j = R$）的理想 $I_1, \dots, I_k$ 满足 $R / (I_1 \cdots I_k) \cong R/I_1 \times \cdots \times R/I_k$。

3.2 怎么拼回来（构造逆映射）

令 $M_i = M / m_i$，求 $y_i = M_i^{-1} \bmod m_i$（互素保证存在，用扩展欧几里得算法）。则

$$x = \sum_{i} r_i \, M_i \, y_i \bmod M.$$

道理：$e_i = M_i y_i$ 满足"模 $m_i$ 是 $1$，模其他 $m_j$ 是 $0$"，它是第 $i$ 个分量的"单位向量"。这和Shamir秘密分享里的拉格朗日基多项式 $L_j(x)$ 是完全一样的思路。

3.3 手算例子：韩信点兵

3.4 多项式版本

把 $\mathbb{Z}$ 换成 $F[x]$，把互素的整数换成互素的多项式，定理照样成立。若 $f(x) = \prod_i (x - \alpha_i)$，$\alpha_i$ 两两不同，则

$$F[x]/(f) \cong F \times F \times \cdots \times F,\qquad g(x) \mapsto \big(g(\alpha_1), \dots, g(\alpha_n)\big).$$

左边的乘法是多项式乘法（卷积，慢）；右边是逐点相乘（快）。这正是 FFT / NTT 的代数本质：取 $\alpha_i$ 为单位根时，正反两个方向都能用分治在 $O(n \log n)$ 内完成。

总结