数论初步

这一页教你整数在除法之下的结构：整除、最大公因数、素数分解，以及由此建立的同余运算体系。学完之后，你能手工执行欧几里得算法与扩展欧几里得算法、判断线性同余方程是否有解并求解、用中国剩余定理和费马小定理化简大数模幂，并能完整走一遍 RSA 的小例子、说清它的安全性从哪里来。

1. 整除与带余除法

定义（整除）。 设 $a,b$ 为整数且 $a\ne 0$。若存在整数 $c$ 使 $b=ac$，则称 $a$ 整除 $b$，记作 $a\mid b$；否则记 $a\nmid b$。当 $a\mid b$ 时，称 $a$ 是 $b$ 的因数（约数），$b$ 是 $a$ 的倍数。

整除关系有几条直接由定义可验证的性质：若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$（传递性）；若 $a\mid b$ 且 $a\mid c$，则对任意整数 $x,y$ 有 $a\mid (bx+cy)$（线性组合封闭）。第二条是后面一切论证的发动机：要证 $a$ 整除某个复杂的式子，把它凑成 $a$ 的两个已知倍数的线性组合即可。

定理（带余除法）。 对任意整数 $a$ 与正整数 $d$，存在唯一的整数 $q$（商）与 $r$（余数），使得

$$a=dq+r,0\le r<d.$$

存在性由”不断减 $d$ 直到落入 $[0,d)$“给出，唯一性用反证：若 $a=d{q}_1+r_1=d{q}_2+r_2$ 且 $r_1\ge r_2$，则 $d(q_1-q_2)=r_2-r_1$，右边绝对值小于 $d$，只可能是 $0$。余数 $r$ 也记作 $a\mathrm{mod}d$。注意计算机语言里的 % 对负数的结果可能为负，数学上总取非负余数。

2. 最大公因数、互素与欧几里得算法

定义。 不全为零的两个整数的最大公因数 $\gcd (a,b)$ 是同时整除 $a,b$ 的最大正整数；最小公倍数 $\text{lcm}(a,b)$ 是同时是 $a,b$ 倍数的最小正整数。若 $\gcd (a,b)=1$，称 $a$ 与 $b$ 互素（coprime）。两者由公式

$$\gcd (a,b)\cdot \text{lcm}(a,b)=|ab|$$

联系起来，所以实际计算只需管 gcd。两个有用的推论：$\gcd (a,b)=\gcd (a,b-a)$（差分不变），更一般地 $\gcd (a,b)=\gcd (a,b\mathrm{mod}a)$——这正是欧几里得算法的依据。

算法（欧几里得）。 反复取余替换：

$$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)=\gcd (a\mathrm{mod}b,b\mathrm{mod}(a\mathrm{mod}b))=\cdots =\gcd (r,0)=r,$$

序列严格递减且非负，必在有限步内到达余数 $0$，最后一个非零余数即答案。每步把一对数换成一个严格更小的数，至多 $O(\log \min (a,b))$ 步。

定理。 对任意正整数 $a,b$，

$$\gcd (a,b)=\gcd (b,a\mathrm{mod}b).$$

证明。 只需证明两边的整除集相同，即 $d\mid a$ 且 $d\mid b$ 当且仅当 $d\mid b$ 且 $d\mid (a\mathrm{mod}b)$。写成带余除法 $a=bq+r$，其中 $q=\lfloor a/b\rfloor$，$r=a\mathrm{mod}b$。

• ($\Rightarrow$) 若 $d\mid a$ 且 $d\mid b$，则 $r=a-bq$ 是 $a,b$ 的线性组合，故 $d\mid r$。
• ($\Leftarrow$) 若 $d\mid b$ 且 $d\mid r$，则 $a=bq+r$ 是 $b,r$ 的线性组合，故 $d\mid a$。

两边整除集完全一致，最大的正公因数自然相等。$■$

定理（Bézout）。 对任意不全为零的整数 $a,b$，存在整数 $x,y$ 使

$$ax+by=\gcd (a,b),$$

且 $\gcd (a,b)$ 是 $a,b$ 所有线性组合 $ax+by$ 中最小的正整数。证明思路：考虑所有正线性组合的集合，取其最小元 $s$，用带余除法证明 $s$ 同时整除 $a$ 和 $b$（否则余数给出更小的正线性组合，矛盾），故 $s\le \gcd (a,b)$；而 $\gcd (a,b)$ 整除任何线性组合，故 $\gcd (a,b)\le s$。两者相等。

Bézout 的逆方向同样常用：若存在 $x,y$ 使 $ax+by=1$，则 $\gcd (a,b)=1$——找一个等于 $1$ 的线性组合，就是证明互素的最直接办法。

算法（扩展欧几里得）。 欧几里得算法的每一步都是线性方程 $r_i=r_{i-2}-q_i{r}_{i-1}$，把每个余数回代成 $a,b$ 的线性组合，递推到末态即得所求的 $x,y$。

例 1. 求 $\gcd (252,105)$，并求 $x,y$ 使 $252x+105y=\gcd (252,105)$。

解. 辗转相除：

$$252=2\cdot 105+42,105=2\cdot 42+21,42=2\cdot 21+0.$$

最后一个非零余数是 $21$，故 $\gcd (252,105)=21$。回代：

$$21=105-2\cdot 42=105-2(252-2\cdot 105)=5\cdot 105-2\cdot 252.$$

所以 $x=-2,y=5$，即 $252\times (-2)+105\times 5=21$。作为副产品，把等式两边除以 $21$ 得 $12\times (-2)+5\times 5=1$，说明 $12$ 与 $5$ 互素。$■$

扩展欧几里得是本章最该练熟的手艺：解线性同余方程、求模逆元、实现 RSA 的密钥生成，全部以它为子程序。

3. 算术基本定理

定理（算术基本定理）。 每个大于 $1$ 的整数 $n$ 都可以唯一地（不计因子顺序）分解为素数的乘积：

$$n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k},p_1<p_2<\cdots <p_k\text{ 为素数},a_i\ge 1.$$

存在性由强归纳给出：$n$ 本身是素数则已；否则 $n=ab$ 且 $1<a,b<n$，归纳假设给出 $a,b$ 各自的分解，拼起来即得 $n$ 的分解。

唯一性的核心是下面这条引理（Euclid 引理）：

若素数 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$。

引理的证明用 Bézout：若 $p\nmid a$，则 $\gcd (p,a)=1$（素数的正因数只有 $1,p$），于是存在 $x,y$ 使 $px+ay=1$；两边乘 $b$ 得 $pbx+aby=b$。左边两项都被 $p$ 整除（$p\mid ab$ 已知），故 $p\mid b$。

有了引理，唯一性用最小反例法：设 $n$ 是有两种不同素因子分解的最小正整数，$n=p_1{p}_2\cdots p_s=q_1{q}_2\cdots q_t$。则 $p_1\mid q_1\cdots q_t$，由引理反复使用，$p_1$ 必整除某个 $q_j$；但 $q_j$ 是素数，只能 $p_1=q_j$。两边约去 $p_1$ 得到比 $n$ 更小的两种分解——与 $n$ 的最小性矛盾。$■$

算术基本定理解释了为什么 gcd 和 lcm 都能”按素因子位”计算：$\gcd$ 取每个素因子指数的最小值，$\text{lcm}$ 取最大值。唯一性是整个定理的灵魂——它保证了”素因子多重集”是整数的一个良定义的内在特征，而不只是某种计算结果。

4. 素数

定义。 大于 $1$ 且正因数只有 $1$ 和自身的整数叫素数；大于 $1$ 的非素数叫合数。$1$ 两个都不是，是乘法结构的单位元，单独分类。

定理（素数有无穷多个，欧几里得）。 存在无穷多个素数。

证明. 反设只有有限个素数 $p_1,p_2,\dots ,p_k$。构造

$$N=p_1{p}_2\cdots p_k+1.$$

$N>1$，由算术基本定理它必有素因子。但每个 $p_i$ 除 $N$ 都余 $1$（$N$ 比 $p_1\cdots p_k$ 多 $1$），所以没有任何一个 $p_i$ 整除 $N$——矛盾。故素数无穷多。$■$

注意这个证明不是”把所有已知素数相乘加 $1$ 必得素数”：$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\times 509$。它说的是 $N$ 的素因子一定不在已知列表里。

素数判定。 若合数 $n$ 有因子 $d$ 满足 $\sqrt{n}<d<n$，则 $n/d$ 是小于 $\sqrt{n}$ 的因子。所以 $n$ 是合数当且仅当它有一个不超过 $\sqrt{n}$ 的素因子。判定 $n$ 是否为素数，只需用不超过 $\sqrt{n}$ 的素数试除——这就是试除法，$O(\sqrt{n})$ 次整除。工程上使用的 Miller–Rabin 等概率性素性测试快得多，RSA 生成密钥时用它筛大素数。

两个著名的未解决问题（只提名字与含义）：

• 梅森素数：形如 $M_p=2^p-1$（$p$ 为素数）的素数。是发现超大素数的主要渠道，但绝大多数 $M_p$ 是合数，是否有无穷多个梅森素数未知。
• 孪生素数猜想：相差 $2$ 的素数对（如 $3,5$；$17,19$）是否有无穷多对，至今未证（2013 年张益唐证明了”有无穷多对间距有限”的弱化形式）。

5. 同余

定义。 设 $m$ 为正整数，$a,b$ 为整数。若 $m\mid (a-b)$，称 $a$ 与 $b$ 同余模 $m$，记作

$$a\equiv b(\mathrm{mod}m).$$

$m$ 叫模。等价地，$a\equiv b(\mathrm{mod}m)$ 当且仅当 $a,b$ 被 $m$ 除的余数相同。同余是整数集上的等价关系：自反（$m\mid 0$）、对称（$m\mid (a-b)\Rightarrow m\mid (b-a)$）、传递（$m\mid (a-b),m\mid (b-c)\Rightarrow m\mid (a-c)$）。于是全体整数被划分成 $m$ 个同余类（等价类）

$$[0],[1],\dots ,[m-1],$$

每个类里的数在模 $m$ 意义下完全不可区分——这就是”模 $m$ 算术”的论域，常记作 ${\mathbb{Z}}_m$ 或 $\mathbb{Z}/m\mathbb{Z}$。

运算保持。 若 $a\equiv b(\mathrm{mod}m)$ 且 $c\equiv d(\mathrm{mod}m)$，则

$$a+c\equiv b+d,a-c\equiv b-d,ac\equiv bd(\mathrm{mod}m).$$

证明都是直接凑差：$ac-bd=a(c-d)+d(a-b)$，右边两项都是 $m$ 的倍数。注意：没有除法保持，“约分”有额外条件（见下）。同余保持加、减、乘，意味着任何整系数多项式也保持：$a\equiv b(\mathrm{mod}m)$ 蕴含 $f(a)\equiv f(b)(\mathrm{mod}m)$。

消去律。 若 $ca\equiv cb(\mathrm{mod}m)$，能推出 $a\equiv b(\mathrm{mod}m)$ 吗？先看反例：$2\cdot 3\equiv 2\cdot 7(\mathrm{mod}8)$（两边都是 $6$ 和 $14$，差 $8$），但 $3\not\equiv 7(\mathrm{mod}4)$……事实上 $3\not\equiv 7(\mathrm{mod}8)$。问题出在 $\gcd (2,8)=2\ne 1$。准确的说法是：

若 $ca\equiv cb(\mathrm{mod}m)$，则 $a\equiv b(\mathrm{mod}\frac{m}{\gcd (c,m)})$。特别地，当 $\gcd (c,m)=1$ 时可放心约去 $c$，得 $a\equiv b(\mathrm{mod}m)$。

证明. $ca\equiv cb(\mathrm{mod}m)$ 即 $m\mid c(a-b)$。写 $g=\gcd (c,m)$，$c=g{c}^{\prime }$，$m=g{m}^{\prime }$，则 $\gcd (c^{\prime },m^{\prime })=1$。条件变为 $g{m}^{\prime }\mid g{c}^{\prime }(a-b)$，即 $m^{\prime }\mid c^{\prime }(a-b)$；因 $\gcd (c^{\prime },m^{\prime })=1$，由 Euclid 引理得 $m^{\prime }\mid (a-b)$，即 $a\equiv b(\mathrm{mod}{m}^{\prime })$。$■$

直观地说：模 $m$ 下唯一真正能”除以 $c$“的元素，是与 $m$ 互素的 $c$——此时存在 $c^{-1}$（见下节），乘过去就是合法的约分。

6. 线性同余方程

方程 $ax\equiv b(\mathrm{mod}m)$ 是本章的核心对象。“解”指的是一个同余类，而非单个整数。

定理。 设 $a,b$ 为整数，$m$ 为正整数，$g=\gcd (a,m)$。方程 $ax\equiv b(\mathrm{mod}m)$

• 有解 当且仅当 $g\mid b$；
• 此时在模 $m$ 下恰有 $g$ 个互不相同的解；若 $x_0$ 是一个解，全部解为 $x\equiv x_0+k\cdot \frac{m}{g}(\mathrm{mod}m)$，$k=0,1,\dots ,g-1$。

证明. $ax\equiv b(\mathrm{mod}m)$ 等价于存在整数 $y$ 使 $ax-my=b$，即二元一次不定方程。Bézout 定理说 $a\mathbb{Z}+m\mathbb{Z}=g\mathbb{Z}$，所以方程有整数解当且仅当 $g\mid b$。有解时设 $(x_0,y_0)$ 为一解，通解为 $x=x_0+k\cdot m/g$，$y=y_0+k\cdot a/g$（$k\in \mathbb{Z}$），其中 $x$ 模 $m$ 恰好取 $g$ 个不同值。$■$

求 $x_0$ 的实操路径：用扩展欧几里得求出 $s,t$ 使 $as+mt=g$（这里 $s$ 就是 $a$ 模 $m$ 的”准逆元”），两边乘 $b/g$ 得

$$a\frac{sb}{g}\equiv b(\mathrm{mod}m),$$

所以 $x_0\equiv sb/g(\mathrm{mod}m)$。当 $g=1$ 时公式最干净：$x\equiv sb(\mathrm{mod}m)$，其中 $as\equiv 1(\mathrm{mod}m)$，这个 $s$ 称为 $a$ 模 $m$ 的逆元，记 $a^{-1}$，是模算术里”除法”的替身。

例 2. 解 $17x\equiv 5(\mathrm{mod}26)$。

解. 先算 $\gcd (17,26)$：$26=1\cdot 17+9$，$17=1\cdot 9+8$，$9=1\cdot 8+1$，$8=8\cdot 1$，得 $g=1$，故方程有唯一解模 $26$。回代求逆元：

$$1=9-8=9-(17-9)=2\cdot 9-17=2(26-17)-17=2\cdot 26-3\cdot 17.$$

所以 $-3\cdot 17\equiv 1(\mathrm{mod}26)$，即 $17^{-1}\equiv -3\equiv 23(\mathrm{mod}26)$。两边乘 $23$：

$$x\equiv 23\times 5=115\equiv 115-4\times 26=11(\mathrm{mod}26).$$

检验： $17\times 11=187=7\times 26+5\equiv 5(\mathrm{mod}26)$，正确。$■$

7. 中国剩余定理

定理（两模版本）。 设 $m_1,m_2$ 为互素的正整数，$a_1,a_2$ 为任意整数。则同余方程组

$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1),\\ x\equiv a_2(\mathrm{mod}{m}_2)\end{array}$$

在模 $m_1{m}_2$ 下有唯一解。

证明与构造. 由 Bézout，存在 $s_1,s_2$ 使 $s_1{m}_1+s_2{m}_2=1$。取

$$x=a_1{s}_2{m}_2+a_2{s}_1{m}_1.$$

模 $m_1$ 看：$s_1{m}_1\equiv 0$，而 $s_2{m}_2=1-s_1{m}_1\equiv 1$，故 $x\equiv a_1$；同理 $x\equiv a_2(\mathrm{mod}{m}_2)$。存在性得证。唯一性：若 $x,x^{\prime }$ 都是解，则 $x-x^{\prime }$ 同时被 $m_1,m_2$ 整除，故被 $\text{lcm}(m_1,m_2)=m_1{m}_2$ 整除（互素时 gcd 为 $1$），即 $x\equiv x^{\prime }(\mathrm{mod}{m}_1{m}_2)$。$■$

互素条件不可去掉：$x\equiv 1(\mathrm{mod}2)$ 与 $x\equiv 2(\mathrm{mod}4)$ 无解，因为前者要求 $x$ 奇、后者要求 $x$ 偶。

例 3. 解 $\{\begin{array}{l}x\equiv 2(\mathrm{mod}3),\\ x\equiv 4(\mathrm{mod}7).\end{array}$

解. 两模互素，模 $21$ 下有唯一解。由第二个同余设 $x=7k+4$，代入第一个：$7k+4\equiv k+1\equiv 2(\mathrm{mod}3)$，得 $k\equiv 1(\mathrm{mod}3)$，取 $k=1$，得 $x=11$。

检验： $11\mathrm{mod}3=2$，$11\mathrm{mod}7=4$，全部解为 $x\equiv 11(\mathrm{mod}21)$。$■$

一般版（一句话）： 对 $k$ 个两两互素的模 $m_1,\dots ,m_k$ 和任意余数 $a_1,\dots ,a_k$，方程组 $x\equiv a_i(\mathrm{mod}{m}_i)$ 在模 $M=m_1\cdots m_k$ 下有唯一解，构造取 $x={\sum }_i{a}_i{M}_i{y}_i$，其中 $M_i=M/m_i$、$y_i$ 是 $M_i$ 模 $m_i$ 的逆元。它等价于环同构 $\mathbb{Z}/M\mathbb{Z}\cong {\prod }_i\mathbb{Z}/m_i\mathbb{Z}$：一个模大数的对象，可以无损拆成模若干小数的对象分别处理——这正是 RSA 解密用 CRT 加速、以及分布式计数里”分桶再合并”的数学原型。

8. 费马小定理与欧拉定理

定理（费马小定理）。 设 $p$ 为素数，$a$ 为整数且 $p\nmid a$，则

$$a^{p-1}\equiv 1(\mathrm{mod}p).$$

（对任意整数 $a$ 也有变形 $a^p\equiv a(\mathrm{mod}p)$。）

证明思路. 模 $p$ 的非零剩余 $\{1,2,\dots ,p-1\}$ 构成乘法群。对每个 $p\nmid a$，集合 $\{a,2a,\dots ,(p-1)a\}$ 模 $p$ 仍是同一集合（$ia\equiv ja(\mathrm{mod}p)$ 蕴含 $i\equiv j$，因为它们可约去 $a$）。两集合元素各自相乘：

$$a\cdot 2a\cdots (p-1)a\equiv 1\cdot 2\cdots (p-1)(\mathrm{mod}p),$$

即 $(p-1)!a^{p-1}\equiv (p-1)!(\mathrm{mod}p)$。$p$ 是素数，$\gcd ((p-1)!,p)=1$，可以约去阶乘，得 $a^{p-1}\equiv 1$。$■$

定理（欧拉定理）。 设 $m\ge 2$，$a$ 为整数且 $\gcd (a,m)=1$，则

$$a^{\phi (m)}\equiv 1(\mathrm{mod}m),$$

其中 欧拉函数 $\phi (m)$ 等于 $1,2,\dots ,m$ 中与 $m$ 互素的整数个数。$m=p$ 为素数时 $\phi (p)=p-1$，费马小定理是它的特例。若 $m=pq$ 为两不同素数之积，则 $\phi (m)=(p-1)(q-1)$——这个公式下一节就要用到。

证明思路. 把费马小定理证明里的”全部非零剩余”换成”模 $m$ 的简化剩余系”（即 $\phi (m)$ 个与 $m$ 互素的代表元），用 $\gcd (a,m)=1$ 保证乘 $a$ 只是重排该集合，完全相同的论证给出 $a^{\phi (m)}\equiv 1$。$■$

这两个定理的价值在于把巨大的指数压小：指数只需模 $p-1$（或 $\phi (m)$）取余。配合快速幂（平方–乘，$O(\log e)$ 次乘法），$a^e\mathrm{mod}m$ 可以在指数有几百位时照样秒算——这正是模幂能成为加密引擎的原因。

例 4. 计算 $2^{100}\mathrm{mod}7$。

解. $7$ 是素数且 $7\nmid 2$，费马小定理给出 $2^6\equiv 1(\mathrm{mod}7)$。把指数按 $6$ 分解：$100=6\times 16+4$，故

$$2^{100}=(2^6{)}^{16}\cdot 2^4\equiv 1^{16}\cdot 16\equiv 16-14=2(\mathrm{mod}7).$$

答案 $2$。 若不用定理而硬算 $2^{100}$，那是一个 31 位的数；用定理只算了两次小乘法。快速幂的写法是相同的思想：$2^{100}=2^{64}\cdot 2^{32}\cdot 2^4$，逐次平方取模，任何 $a^e\mathrm{mod}m$ 都只需 $O(\log e)$ 步。$■$

9. RSA：一次完整的加密与解密

RSA（Rivest–Shamir–Adleman, 1977）是第一个实用的公钥密码体制：加密密钥可以公开，解密密钥只有接收方持有。它的全部数学就是前面八节的组装。

密钥生成。

1. 选两个大素数 $p,q$，计算 $n=pq$（公钥模数）和 $\phi (n)=(p-1)(q-1).$
2. 选一个 $e$ 满足 $1<e<\phi (n)$ 且 $\gcd (e,\phi (n))=1$，公开 $(n,e)$ 作为公钥。
3. 用扩展欧几里得求 $d$ 使 $ed\equiv 1(\mathrm{mod}\phi (n))$，$1<d<\phi (n)$，保留 $(n,d)$ 作为私钥。$p,q,\phi (n)$ 销毁或封存。

加密：消息 $m$（$0\le m<n$）映射为 $c\equiv m^e(\mathrm{mod}n)$。解密：计算 $m^{\prime }\equiv c^d(\mathrm{mod}n)$。

为什么解密能还原？ 因为 $ed=1+k\phi (n)$。若 $\gcd (m,n)=1$，欧拉定理直接给出

$$c^d\equiv m^{ed}=m^{1+k\phi (n)}=m\cdot (m^{\phi (n)}{)}^k\equiv m(\mathrm{mod}n).$$

$\gcd (m,n)>1$ 的少数情形用中国剩余定理拆到模 $p$、模 $q$ 上分别验证，结论一样。所以 $m^{\prime }\equiv m(\mathrm{mod}n)$，而 $0\le m<n$，两边相等。

例 5. 取 $p=3,q=11$（实战里应是几百位的大素数，这里为了手算）。则

$$n=33,\phi (n)=(3-1)(11-1)=20.$$

选 $e=7$（$\gcd (7,20)=1$，满足条件）。求私钥：扩展欧几里得，$20=2\times 7+6$，$7=1\times 6+1$，回代得 $1=7-6=7-(20-2\times 7)=3\times 7-20$，即 $3\times 7\equiv 1(\mathrm{mod}20)$，所以 $d=3$。

公钥 $(n,e)=(33,7)$，私钥 $(n,d)=(33,3)$。发消息 $m=2$（要求 $m<n$）：

加密： $c\equiv 2^7=128\equiv 128-3\times 33=29(\mathrm{mod}33)$，发出密文 $29$。

解密： $m^{\prime }\equiv 29^3(\mathrm{mod}33)$。用快速幂：$29^2=841\equiv 841-25\times 33=841-825=16(\mathrm{mod}33)$，$29^3\equiv 16\times 29=464\equiv 464-14\times 33=464-462=2(\mathrm{mod}33)$。还原出 $m^{\prime }=2$。也可以心算校验：$29\equiv 2(\mathrm{mod}3)$、$29\equiv 7(\mathrm{mod}11)$，由中国剩余定理只需验证 $2^3\equiv 2(\mathrm{mod}3)$ 和 $7^3=343\equiv 2(\mathrm{mod}11)$，都对。$■$

为什么安全？ 攻击者知道 $n,e,c$，要算 $d$ 或直接从 $c$ 开 $e$ 次方，都要知道 $\phi (n)=(p-1)(q-1)$；而 $\phi (n)$ 与 $n$ 的差 $n-\phi (n)+1=p+q$ 一旦泄露就能解出 $p,q$。所以从 $n$ 分解出 $p,q$ 是已知的攻击捷径——但对几百位的大数，大整数分解目前没有已知的多项式时间算法，经典计算机上不可行；模幂运算（加密、解密、窃听者做的任何事）却只要 $O(\log )$ 次乘法，极其便宜。安全性就建立在”乘起来容易、拆回去难”这条不对称上。（Shor 的量子算法能分解大整数，所以量子计算成熟后 RSA 需被格密码等替代方案替换——这是选参数时要留意的长期风险。）

注意教科书常演示的另一方向隐患：同一条消息 $m$ 用同一公钥加密多次会泄露统计信息，实际协议要加随机填充（如 OAEP）。另外模数 $n$ 必须足够大（当前实践 $\ge 2048$ 位），小模数下试除法直接分解。

常见错误

• 同余两边随意约分。 $ca\equiv cb(\mathrm{mod}m)$ 推 $a\equiv b(\mathrm{mod}m)$ 只在 $\gcd (c,m)=1$ 时成立；一般只能约到模 $m/\gcd (c,m)$。正确做法：确认 $\gcd (c,m)=1$ 后乘逆元 $c^{-1}$，而不是”两边除掉 $c$”。
• 忽略线性同余方程的有解条件。 $ax\equiv b(\mathrm{mod}m)$ 有解当且仅当 $\gcd (a,m)\mid b$。拿到方程先算 gcd 判可解性，别直接套逆元公式——逆元只在 $\gcd (a,m)=1$ 时存在。
• 中国剩余定理忘了互素前提。 模不互素时可能无解或解不唯一（判据：同余在模 $\gcd (m_1,m_2)$ 下必须相容）。
• 费马小定理用错条件。 它要求模是素数且 $p\nmid a$；模为合数时要用欧拉定理且 $\gcd (a,m)=1$。比如 $2^4\equiv 1(\mathrm{mod}5)$ 对，但 $2^2\equiv 1(\mathrm{mod}3)$ 不能套”指数模 $3-1$“以外的推广。
• RSA 手算例子里 $e$ 与 $\phi (n)$ 不互素就求逆元。 选 $e$ 前先验证 $\gcd (e,\phi (n))=1$，否则 $d$ 根本不存在。
• 负数的余数符号混乱。 数学约定 $a\mathrm{mod}d\in [0,d)$；$-7\mathrm{mod}3=2$ 而不是 $-1$。

练习

1. 用欧几里得算法求 $\gcd (1071,462)$，并求整数 $x,y$ 使 $1071x+462y=\gcd (1071,462)$。 答案： $1071=2\cdot 462+147$，$462=3\cdot 147+21$，$147=7\cdot 21$，故 gcd 为 $21$。回代：$21=462-3\cdot 147=462-3(1071-2\cdot 462)=7\cdot 462-3\cdot 1071$，即 $x=-3,y=7$。

2. 判断方程 $15x\equiv 6(\mathrm{mod}21)$ 是否有解；若有，写出全部解。 答案： $\gcd (15,21)=3$，$3\mid 6$，有解，共 $3$ 个解模 $21$。两边同除以 $3$ 化简为 $5x\equiv 2(\mathrm{mod}7)$；$5\times 3=15\equiv 1(\mathrm{mod}7)$，故 $5^{-1}\equiv 3$，$x\equiv 6(\mathrm{mod}7)$。全部解：$x\equiv 6,13,20(\mathrm{mod}21)$。

3. 计算 $3^{2026}\mathrm{mod}7$。 答案： 费马小定理 $3^6\equiv 1(\mathrm{mod}7)$；$2026=6\times 337+4$，所以 $3^{2026}\equiv 3^4=81\equiv 4(\mathrm{mod}7)$。

4. 一个正整数除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$，求它的最小值。 答案： 三模两两互素，CRT 保证模 $105$ 唯一解。由 $x\equiv 2(\mathrm{mod}3)$ 与 $x\equiv 2(\mathrm{mod}7)$ 得 $x\equiv 2(\mathrm{mod}21)$；设 $x=21k+2$，代入 $21k+2\equiv k+2\equiv 3(\mathrm{mod}5)$，得 $k\equiv 1(\mathrm{mod}5)$，取 $k=1$ 得最小值 $x=23$。

5. 取 RSA 参数 $p=3,q=7,e=5$。写出公钥与私钥，并将消息 $m=4$ 加密后解密，验证能还原。 答案： $n=21$，$\phi (n)=12$，$e=5$ 与 $12$ 互素。由 $5\times 5=25\equiv 1(\mathrm{mod}12)$ 得 $d=5$。公钥 $(21,5)$，私钥 $(21,5)$。加密：$c\equiv 4^5=1024\equiv 1024-48\times 21=16(\mathrm{mod}21)$。解密：$16^2=256\equiv 4(\mathrm{mod}21)$，$16^5=16^4\cdot 16\equiv 4^2\cdot 16=256\equiv 4(\mathrm{mod}21)$，还原 $m=4$。（此例中公钥私钥指数恰好相同，是参数太小的巧合；换 $e=11$ 可得 $d=11$ 亦然，换 $e=7$ 则 $d=7$——因为 $\phi (21)=12$ 的自逆元多。实践里 $p,q$ 大时不会这样。）

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：图论基础
• NEXT：递归与递推