密码学数学基础 笔记 5：求解线性同余方程，用中国剩余定理合并不同模数，并将多项式同余问题归结到素数幂

同余方程与中国剩余定理

上一篇把整数按模数分为剩余类。这一篇把未知数放进同余式，讨论何时有解、有多少个不同的解，以及如何把多个模数下的条件合并起来

线性同余方程

考虑 $m>1$ 时的方程（模 $1$ 时任意整数都是解）

$$ax\equiv c\pmod m$$

它等价于整数方程 $ax-my=c$。设 $d=\gcd(a,m)$，由 Bézout 等式与线性丢番图方程的结论，有解的充要条件是

$$\boxed{d\mid c}$$

若条件成立，把系数和模数都除以 $d$：

$$\frac adx\equiv\frac cd\pmod{m/d}$$

因为 $\gcd(a/d,m/d)=1$，可用逆元找到唯一的解类 $x\equiv t\pmod{m/d}$。若仍以原模数 $m$ 计数，这个类对应恰好 $d$ 个不同的解类：

$$\boxed{x\equiv t+j\frac md\pmod m,\qquad j=0,1,\ldots,d-1}$$

例如 $6x\equiv8\pmod{14}$，有 $d=2$。约化为 $3x\equiv4\pmod7$，而 $3^{-1}\equiv5\pmod7$，所以 $x\equiv6\pmod7$。模 $14$ 的两个解为 $x\equiv6,13\pmod{14}$。如果右边改成 $9$，因为 $2\nmid9$，方程无解

对于整数方程，模运算还可用于排除解：若整数解存在，它在每个模数下都必须给出同余解。因此找到一个模数使同余方程无解，就证明原整数方程无解

中国剩余定理

现在考虑不同模数下的条件：

$$x\equiv a_i\pmod{m_i},\qquad i=1,\ldots,s$$

中国剩余定理（CRT）说：如果正整数 $m_1,\ldots,m_s$ 两两互素，那么任意指定的 $a_i$ 都对应唯一的模 $M=\prod_i m_i$ 的解类。这里“两两互素”比“全部模数的最大公因数为 $1$”更强

构造解

令

$$M_i=\frac{M}{m_i},\qquad N_i\equiv M_i^{-1}\pmod{m_i}$$

逆元存在，因为 $M_i$ 与 $m_i$ 互素。于是

$$\boxed{x\equiv\sum_{i=1}^s a_iM_iN_i\pmod M}$$

$M_iN_i$ 在模 $m_i$ 下为 $1$，在其他各模数下为 $0$，所以求和后恰好得到所有指定余数。若 $x,y$ 都满足条件，则每个 $m_i$ 都整除 $x-y$；两两互素意味着 $M\mid x-y$，故解类唯一

以《孙子算经》的经典问题为例：

$$x\equiv2\pmod3,\qquad x\equiv3\pmod5, \qquad x\equiv2\pmod7$$

这里 $M=105$，三个“坐标选择器”可以取 $70,21,15$：各自在对应模数下为 $1$，在另外两个模数下为 $0$。所以

$$x\equiv2\cdot70+3\cdot21+2\cdot15 =233\equiv23\pmod{105}$$

全部整数解是 $23+105t$，其中 $t\in\mathbb Z$。$23$ 是区间 $[0,105)$ 中唯一的解

非互素模数的兼容条件

如果只有两个模数 $m,n$，条件 $x\equiv a\pmod m$、$x\equiv b\pmod n$ 有解的充要条件是

$$\boxed{a\equiv b\pmod{\gcd(m,n)}}$$

必要性是把两个同余式都降到公因数模数下。充分性可以令 $x=a+mt$，再解线性同余式 $mt\equiv b-a\pmod n$。若有解，所有解构成唯一的模 $\operatorname{lcm}(m,n)$ 的类

例如 $x\equiv4\pmod6$ 与 $x\equiv11\pmod{15}$ 不兼容：它们分别要求 $x\equiv1,2\pmod3$

如果原问题是若干个 $a_ix\equiv b_i\pmod{m_i}$，应先对每个方程检查 $\gcd(a_i,m_i)\mid b_i$，约化为 $x\equiv c_i\pmod{m_i/\gcd(a_i,m_i)}$，再合并这些标准同余式

混合进制重建

CRT 也可以通过逐层选“数字”来计算。对两个互素模数，先取 $x\equiv a_1\pmod{m_1}$，写成

$$x=a_1+m_1u$$

代入第二个条件，得到

$$u\equiv(a_2-a_1)m_1^{-1}\pmod{m_2}$$

取 $0\le a_1<m_1$ 和 $0\le u<m_2$，就直接得到 $[0,m_1m_2)$ 中的唯一代表元。更一般地，逐层写为

$$x=x_1+m_1x_2+m_1m_2x_3+\cdots, \qquad 0\le x_i<m_i,$$

并用下一个同余条件确定下一个数字。这是 Garner 算法的基本想法。固定模数时，所需逆元可以预先计算

这种分解在密码学中有实际用途。例如 RSA 私钥已知 $n=pq$ 的两个素因子时，可分别计算 $c^d\bmod p$ 和 $c^d\bmod q$，再通过 CRT 重建模 $n$ 的结果。对于两个模数，预先求 $C=p^{-1}\bmod q$，若两边结果是 $a_p,a_q$，可取

$$u\equiv(a_q-a_p)C\pmod q,\qquad x=a_p+pu$$

另一方面，CRT 也说明了未编码的教材式 RSA 会泄露代数关系。若相同消息 $m$ 用小指数 $e=3$ 发给三个接收者，模数 $n_1,n_2,n_3$ 两两互素，且 $m<\min n_i$，则可从三份密文 $c_i\equiv m^3\pmod{n_i}$ 重建 $m^3\bmod n_1n_2n_3$。由于 $m^3<n_1n_2n_3$，得到的就是整数 $m^3$，再取整数立方根便恢复 $m$。实际加密需要经过明确规定且经过分析的编码方案，例如 RSA-OAEP

一般多项式同余方程

令 $f\in\mathbb Z[X]$，考虑

$$f(x)\equiv0\pmod m$$

若 $m=\prod_{i=1}^s p_i^{e_i}$ 是标准素因数分解，则不同的素数幂两两互素。于是

$$f(x)\equiv0\pmod m \quad\Longleftrightarrow\quad f(x)\equiv0\pmod{p_i^{e_i}}\quad\text{对所有 }i$$

CRT 将每一组局部解唯一拼成一个模 $m$ 的解。记 $N_f(n)$ 为 $f(x)\equiv0\pmod n$ 的不同解类数，就有

$$\boxed{N_f(m)=\prod_{i=1}^s N_f(p_i^{e_i})}$$

例如 $x^3-x=x(x-1)(x+1)$ 对任意整数都能被 $2$ 和 $3$ 整除，故 $x^3-x\equiv0\pmod6$ 有六个解类，比多项式的次数还多。素数模数下的情形不同：若 $f$ 模 $p$ 化简后是非零的 $d$ 次多项式，则它在域 $\mathbb F_p$ 中至多有 $d$ 个根。每找到一个根，都能提出一个一次因子；非零多项式不能含有超过次数的互异一次因子

这个根数上界还给出 Wilson 定理。费马小定理说明 $1,\ldots,p-1$ 都是 $X^{p-1}-1$ 在 $\mathbb F_p$ 中的根。两边都是首一的 $p-1$ 次多项式，因此

$$X^{p-1}-1=\prod_{a=1}^{p-1}(X-a)\quad\text{在 }\mathbb F_p[X]\text{ 中}$$

比较常数项，即得 $(p-1)!\equiv-1\pmod p$；$p=2$ 时也直接成立

从模 $p$ 提升到模 $p^e$

CRT 把问题拆到素数幂，但 $p^e$ 不能再拆成两个互素的非平凡因子。因此从模 $p$ 的根出发，逐层提升精度

设 $e\ge2$，$\xi$ 已满足 $f(\xi)\equiv0\pmod{p^{e-1}}$。它在模 $p^e$ 下的 $p$ 个候选代表元是

$$x=\xi+s p^{e-1},\qquad s=0,1,\ldots,p-1$$

将多项式在 $\xi$ 处展开。二次及更高项都被 $p^e$ 整除，因此

$$f(\xi+s p^{e-1})\equiv f(\xi)+s p^{e-1}f'(\xi)\pmod{p^e}$$

写 $f(\xi)=p^{e-1}q$，候选元成为根的条件是一个模 $p$ 的线性方程：

$$\boxed{s f'(\xi)\equiv-q\pmod p}$$

由此分成三种情况：

• 若 $f'(\xi)\not\equiv0\pmod p$，导数可逆，恰有一个 $s$；这就是单根的 Hensel 提升
• 若 $f'(\xi)\equiv0\pmod p$ 且 $q\equiv0\pmod p$，全部 $p$ 个候选元都成立
• 若 $f'(\xi)\equiv0\pmod p$ 且 $q\not\equiv0\pmod p$，没有候选元成立

例如求解 $x^3\equiv2\pmod{125}$。模 $5$ 时 $x=3$ 是根，取 $f(X)=X^3-2$，有 $f'(3)=27\equiv2\pmod5$，所以每层提升唯一。由于 $f(3)=25$，$3$ 本身已是模 $25$ 的根。再从模 $25$ 提升：

$$x=3+25s,\qquad s\cdot2\equiv-\frac{25}{25}=-1\pmod5$$

解得 $s=2$，因此

$$\boxed{x\equiv53\pmod{125}}$$

确实有 $53^3-2=125\cdot1191$。这条路径概括了解多项式同余的常用做法：先在每个素数模数下找根，再向对应的素数幂提升，最后用 CRT 拼回原模数