点击任一公式，可查看并复制 LaTeX 源码。正文、公式及此工具均可单文件离线使用；剪贴板受限时可选中源码手动复制。

费马小定理与初等数论笔记

第四版 · 2026-10-10

从同余、乘法阶和原根，走到RSA与随机分解的概率证明。

本篇以一般推导为主。每个符号在使用时说明含义，每一步推理交代依据；具体例子用于解释容易混淆的地方。第1—12章是连续的主线，第13—17章保留完整基础证明、拓展和练习，可在需要时回查。若主要关心概率证明，先读第8—11章；遇到阶、原根或CRT的疑问，再回到第4—6章。

来源为第一份原对话的21轮、第二份原对话的11轮，以及加权概率补充。第一份对话中的一张公式报错截图仅保留附件引用，未直接查看；正文公式重新排版。第18章提供原问题与章节的对应关系。

第 1 章：同余、消去与模逆元3
第 2 章：费马小定理与指数缩减4
第 3 章：欧拉函数与欧拉定理6
第 4 章：乘法阶与指数的周期8
第 5 章：原根与循环群的含义10
第 6 章：中国剩余定理与余数坐标12
第 7 章：RSA的指数选择与解密正确性14
第 8 章：已知私钥怎样随机分解模数16
第 9 章：成功条件与两个首次到达时间18
第 10 章：取幂的均匀性与到达时间分布21
第 11 章：相等概率为什么是加权平均25
第 12 章：重试、运行时间与RSA结论的范围28
第 13 章：补充证明：逆元、唯一分解与CRT30
第 14 章：补充证明：质数为什么一定有原根39
第 15 章：补充证明：群、阶与欧拉函数计数44
第 16 章：补充：精确概率、统一指数与运行时间50
第 17 章：辨清几个计数问题，再用练习回查54
第 18 章：从原问题回到笔记，以及怎样分享57

第 1 章：同余、消去与模逆元

返回目录

1.1 同余是在比较什么

固定一个正整数 $n$ 作为模数。写 $a \equiv b (\mod n)$ ，意思是 $n$ 整除 $a - b$ ：两个整数相差 $n$ 的整数倍，因此除以 $n$ 的余数相同。例如 $17 \equiv 2 (\mod 5)$ ，因为 $17 - 2 = 3 \cdot 5$ 。

同余不要求两个整数本身相等。它只保留“除以 $n$ 后属于哪一种余数”的信息。以后说“模 $n$ 的一个数”，指的是一个剩余类；计算时可以用 $0, 1, \dots, n - 1$ 中的代表表示它。

为什么可以先取余再计算？若 $a = b + u n$ 、 $c = d + v n$ ，其中 $u, v$ 为整数，那么

a + c = (b + d) + (u + v) n, a c = b d + n (u d + v b + u v n) .

这两个差都含有因子 $n$ ，所以加法和乘法保留同余。重复使用乘法，就得到 $a^{k} \equiv b^{k} (\mod n)$ ，这里 $k$ 是非负整数。这是以后所有模幂运算的依据。

1.2 为什么约分需要互质

在整数等式中，非零因子可以消去；在同余中，需要额外条件。若

a c \equiv b c (\mod n),

我们知道的是 $n ∣ c (a - b)$ 。要推出 $n ∣ (a - b)$ ，必须保证 $c$ 不会替 $a - b$ 承担模数中的质因子。条件 $gcd (c, n) = 1$ 恰好保证这一点。这里 $gcd$ 表示最大公约数，最大公约数为1就是互质。

严格地说，裴蜀等式告诉我们：若 $gcd (c, n) = 1$ ，存在整数 $u, v$ 使 $u c + v n = 1$ 。两边乘 $a - b$ ，得到

a - b = u c (a - b) + v n (a - b) .

右边两项都被 $n$ 整除，所以左边也被 $n$ 整除。于是

gcd (c, n) = 1, a c \equiv b c (\mod n) ⟹ a \equiv b (\mod n) .

不互质时结论确实会失败： $2 \cdot 1 \equiv 2 \cdot 4 (\mod 6)$ ，但 $1 ≢ 4 (\mod 6)$ 。这个例子用于提醒我们检查条件；一般证明仍是上面的裴蜀等式推导。裴蜀等式自身的证明在第13章。

1.3 模逆元怎样代替除法

若 $a b \equiv 1 (\mod n)$ ，就称 $b$ 为 $a$ 的模 $n$ 逆元。它的作用是：乘 $a$ 之后再乘 $b$ ，会恢复原来的剩余类。因此解 $a x \equiv c (\mod n)$ 时，可以两边乘 $b$ ，得到 $x \equiv b c (\mod n)$ 。

逆元存在的充要条件是 $gcd (a, n) = 1$ 。充分性来自裴蜀等式： $a u + n v = 1$ 模 $n$ 后给出 $a u \equiv 1$ 。必要性也直接：若 $a$ 和 $n$ 有大于1的公因子，这个公因子会整除 $a b$ 和 $n$ ，不可能让 $a b$ 与1只相差 $n$ 的倍数。

所以后面证明中出现“消去一个因子”“取逆元”时，互质条件不是形式上的附加语，而是让这一步成立的原因。

第 2 章：费马小定理与指数缩减

返回目录

2.1 定理说了什么

若 $p$ 是质数，且 $p$ 不整除整数 $a$ ，则

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

质数 $p$ 的非零剩余类都与 $p$ 互质，因此第1章的消去律可以使用。这个条件会在证明最后一步发挥作用。

还有一种包含所有整数 $a$ 的形式： $a^{p} \equiv a (\mod p)$ 。若 $p ∤ a$ ，把第一式乘 $a$ 即可；若 $p ∣ a$ ，两边模 $p$ 都为0。反过来，只有在 $p ∤ a$ 时，才能从后一式约去 $a$ ，得到前一式。

2.2 为什么乘法会把非零余数重新排列

考虑非零剩余类 $1, 2, \dots, p - 1$ ，把它们分别乘 $a$ 。要证明乘后的余数仍然是这一整组数，只需排除两种情况。

第一，不会出现0。若 $a i \equiv 0 (\mod p)$ ，因为 $a$ 与 $p$ 互质，可以消去 $a$ ，得到 $i \equiv 0$ ，与 $1 \leq i \leq p - 1$ 矛盾。

第二，不会有两个不同位置产生相同余数。若 $a i \equiv a j (\mod p)$ ，消去 $a$ 得到 $i \equiv j$ 。而 $i, j$ 都在 $1$ 至 $p - 1$ 之间，同余只能意味着 $i = j$ 。

因此，乘后的 $p - 1$ 个余数非零且互不相同；总共只有 $p - 1$ 种非零余数，它们必然把原来的整组数全部占满。这里“重新排列”指的就是这件事，并没有增加或丢失余数。

把这组同余相乘，就有

(a \cdot 1) (a \cdot 2) \dots (a \cdot (p - 1)) \equiv 1 \cdot 2 \dots (p - 1) (\mod p) .

左边含有 $p - 1$ 个 $a$ ，所以可写为 $a^{p - 1} (p - 1)!$ 。两边的 $(p - 1)!$ 都与 $p$ 互质，可以消去。剩下的正是 $a^{p - 1} \equiv 1$ 。

证明的顺序是：互质允许消去 → 乘法没有重复和零 → 整组余数只是重排 → 相乘并消去共同乘积。一般的欧拉定理还会使用同一思路。

2.3 为什么能缩减指数

若 $a^{p - 1} \equiv 1$ ，把非负整数指数 $m$ 写成

m = q (p - 1) + r, 0 \leq r < p - 1,

就得到

a^{m} = (a^{p - 1})^{q} a^{r} \equiv a^{r} (\mod p) .

这一步不是直接对指数套用同余运算法则；依据是每一整段 $p - 1$ 次幂都贡献一个1。例如算 $3^{100} mod 7$ ，由于 $100 = 16 \cdot 6 + 4$ ，只需算 $3^{4} \equiv 4 (\mod 7)$ 。例子中的“对6取余”和“对7取余”承担不同任务：6用于分解指数，7用于计算幂的值。

2.4 应用和使用边界

定理还可以证明整除： $a^{p} \equiv a (\mod p)$ 等价于 $p ∣ (a^{p} - a)$ 。也可以给出逆元：当 $p ∤ a$ 时， $a \cdot a^{p - 2} \equiv 1$ ，所以 $a^{p - 2}$ 是 $a$ 的逆元。

但通过一次类似的幂同余检验，不能反过来保证模数是质数。例如 $341 = 11 \cdot 31$ ，却有 $2^{340} \equiv 1 (\mod 341)$ ，因为 $2^{10} = 1024 \equiv 1 (\mod 341)$ 。费马小定理给的是“质数必满足”的性质，并未证明“满足这个性质的数必为质数”。

第 3 章：欧拉函数与欧拉定理

返回目录

3.1 欧拉函数数的是哪些整数

$φ (n)$ 表示 $1, 2, \dots, n$ 中与 $n$ 互质的整数个数。等价地，它是模 $n$ 可逆剩余类的个数。它数的不是素数，也不是 $n$ 的质因子。

若 $n = \prod_{i = 1}^{k} p_{i}^{e_{i}}$ 是质因数分解，其中 $p_{i}$ 互不相同，那么

φ (n) = n \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}}) .

为什么只出现不同的质因子，而没有直接出现次数 $e_{i}$ ？一个整数与 $n$ 不互质，意味着它被某个 $p_{i}$ 整除。是否被 $p_{i}$ 整除已经决定了它要被排除，不需要再分别排除 $p_{i}^{2}, p_{i}^{3}$ 的倍数。幂次仍包含在前面的 $n$ 中。

3.2 乘积公式为什么就是容斥

先看 $n$ 恰有两个不同质因子 $p, q$ 的情况。在 $1$ 至 $n$ 中， $p$ 的倍数有 $n / p$ 个， $q$ 的倍数有 $n / q$ 个。如果直接都减掉，同时被 $p, q$ 整除的整数会被减两次，所以要补回 $n / (p q)$ 个：

φ (n) = n - \frac{n}{p} - \frac{n}{q} + \frac{n}{p q} = n (1 - \frac{1}{p}) (1 - \frac{1}{q}) .

有更多质因子时，原理相同：减去单个倍数集合，加回两两交集，再减去三重交集，依次交替。展开 $\prod_{i} (1 - 1 / p_{i})$ 时，选一个负项得到一次减法，选两个负项得到交集的加法，选三个负项得到三重交集的减法。乘积展开恰好记录了每种交集和符号。

对于每一个具体整数，这样加减后的总权重是什么？若它不被任何 $p_{i}$ 整除，权重为1；若它被其中 $j \geq 1$ 个整除，权重为 $(1 - 1)^{j} = 0$ 。因此最终恰好保留互质整数。完整容斥展开在第13章。

特别地， $φ (p) = p - 1$ ， $φ (p^{e}) = p^{e} - p^{e - 1}$ 。若 $m, n$ 互质，CRT把模 $m n$ 的可逆类与一对模 $m, n$ 的可逆类对应，因而 $φ (m n) = φ (m) φ (n)$ 。这个对应在第6章解释。

3.3 欧拉定理的证明为什么仍是重排

欧拉定理把质数模数推广到一般模数：若 $n \geq 2$ 且 $gcd (a, n) = 1$ ，则

a^{φ (n)} \equiv 1 (\mod n) .

设 $r_{1}, \dots, r_{φ (n)}$ 代表全部与 $n$ 互质的剩余类。乘 $a$ 后仍互质：若某个质因子同时整除 $a r_{i}$ 和 $n$ ，它必整除 $a$ 或 $r_{i}$ ，而这两种情况都被互质条件排除。不同的 $r_{i}$ 也不会碰到一起： $a r_{i} \equiv a r_{j}$ 可以消去 $a$ 。

于是 $a r_{1}, \dots, a r_{φ (n)}$ 只是这一整组可逆类的重排。相乘得到

a^{φ (n)} r_{1} \dots r_{φ (n)} \equiv r_{1} \dots r_{φ (n)} (\mod n) .

乘积仍与 $n$ 互质，消去后就是欧拉定理。注意，两次消去都检查了互质：先对 $a$ 使用，最后对 $r_{1} \dots r_{φ (n)}$ 使用。

3.4 欧拉指数保证了什么

当 $n = p$ 为质数时， $φ (p) = p - 1$ ，欧拉定理退回费马小定理。对一般互质底数，它同样允许把指数对 $φ (n)$ 取余，推导方式与第2.3节相同。

但 $φ (n)$ 只是一个一定能使幂回到1的指数，不一定最小；下一章会定义这个最小指数。若底数不与模数互质，欧拉定理就不能直接使用。这也是为什么RSA的解密正确性不能只写一句“由欧拉定理”，还必须处理不互质的消息。

第 4 章：乘法阶与指数的周期

返回目录

4.1 阶是最小的“回到1”的指数

若 $gcd (a, n) = 1$ ，定义

d = {ord}_{n} (a) = min {k \geq 1 : a^{k} \equiv 1 (\mod n)} .

这个 $d$ 称为 $a$ 模 $n$ 的乘法阶。它存在，因为欧拉定理已经给出一个符合条件的正指数 $φ (n)$ 。定义只是从所有符合条件的正指数中取最小的一个。

例如模7时， $2, 2^{2}, 2^{3}$ 的余数是 $2, 4, 1$ ，所以 ${ord}_{7} (2) = 3$ ；而费马小定理给的指数是6。这里6没有错，它只是没有声称自己最小。

4.2 为什么其他回到1的指数必为阶的倍数

若 $a^{m} \equiv 1$ ，把 $m$ 除以 $d$ ：

m = q d + r, 0 \leq r < d .

因为 $a^{d} \equiv 1$ ，有 $a^{m} \equiv a^{r}$ ，所以 $a^{r} \equiv 1$ 。如果 $r > 0$ ，它就是一个比 $d$ 更小、还能使幂回到1的正指数，违反 $d$ 的最小性。因此 $r = 0$ ，即 $d ∣ m$ 。

反过来，如果 $d ∣ m$ ， $a^{m}$ 是 $a^{d}$ 的整数次幂，当然同余于1。于是对非负整数 $m$ ，

a^{m} \equiv 1 (\mod n) ⟺ d ∣ m .

把 $m = φ (n)$ 代入，得到 $d ∣ φ (n)$ 。这是比“阶不超过欧拉函数”更强的整除结论，后面的计数需要的是它的整除性。

4.3 对指数取模，为什么不改变幂值的模数

同样把任意非负指数 $k$ 写成 $k = q d + r$ ，有 $a^{k} \equiv a^{r} (\mod n)$ 。因此幂的值由 $k mod d$ 决定。

这里有两个不同的对象： $k$ 是指数，其周期为 $d$ ； $a^{k}$ 是幂值，仍在模 $n$ 下计算。可以记为

k mod d ⟼ a^{k} mod n .

例如 $8$ 模13的阶为4，故 $8^{11} \equiv 8^{3} \equiv 5 (\mod 13)$ 。指数11对4取余，是在寻找循环中的位置；最后的余数5仍是对13计算出来的。后面从 $p$ 转到 $2^{α}$ 时，发生的正是这种“指数周期改变”，不是把幂值的模数换掉。

4.4 怎样求阶，以及一个幂的阶

求阶时不必试所有正整数，只需在 $φ (n)$ 的因数中找最小满足 $a^{d} \equiv 1$ 的 $d$ 。若已知某个合适的指数 $M$ ，可以逐个尝试移除 $M$ 的质因子；每次都检验移除后的幂是否仍为1。

另一个常用结论是：若 $a$ 的阶为 $d$ ，那么 $a^{k}$ 的阶为

{ord}_{n} (a^{k}) = \frac{d}{gcd (d, k)} .

它为什么有这个形状？ $(a^{k})^{m} \equiv 1$ 等价于 $d ∣ k m$ 。写 $d = c d^{'}$ 、 $k = c k^{'}$ ，其中 $c = gcd (d, k)$ ，则条件变成 $d^{'} ∣ k^{'} m$ 。由于 $d^{'}, k^{'}$ 互质，等价于 $d^{'} ∣ m$ ；最小正 $m$ 就是 $d^{'}$ 。对 $k = 0$ ，公式也给出阶1，因为 $a^{0} = 1$ 。

第 5 章：原根与循环群的含义

返回目录

5.1 原根为什么能给所有非零余数编号

模质数 $p$ 的非零剩余类共有 $p - 1$ 个。若某个 $g$ 的阶恰好为 $p - 1$ ，则

g^{0}, g^{1}, \dots, g^{p - 2}

模 $p$ 互不相同。否则若 $g^{i} \equiv g^{j}$ 且 $0 \leq i < j < p - 1$ ，乘 $g^{i}$ 的逆元就得到 $g^{j - i} \equiv 1$ ；而 $0 < j - i < p - 1$ ，与阶的最小性矛盾。

这 $p - 1$ 个不同的非零余数必然遍历全部非零类。这样的 $g$ 称为模 $p$ 的原根。因此每个非零余数 $a$ 都能唯一写为

a \equiv g^{k} (\mod p), 0 \leq k < p - 1.

这里的 $k$ 是 $a$ 在幂循环中的编号。给余数编号，不意味着编号等于余数本身；编号的好处是把乘法转化为指数相加。

5.2 “循环群”是在概括哪件事

把模 $n$ 的全部可逆剩余类记为 $U_{n}$ ，运算是模 $n$ 乘法。它们满足：乘积仍可逆，有单位元1，每个元素有逆元，乘法满足结合律。具有这些性质的集合称为群；“群的阶”表示它有多少个元素，因此 $| U_{n} | = φ (n)$ 。

如果整个群都能写成某个元素的幂，就称为循环群。于是“模质数 $p$ 的非零剩余类构成 $p - 1$ 阶循环群”包含两个结论：它们在乘法下构成群；存在一个原根，能用幂遍历整个群。前一个结论来自逆元与乘法，后一个结论需要证明原根存在，不能混为一件事。

“元素的阶”是回到1所需的最小正指数；“群的阶”是元素总数。它们使用同一个词，但定义不同。有限群中，元素阶整除群阶；第15章用陪集划分证明。对于循环群，我们也可以直接从第4.4节的幂阶公式看出这一点。

5.3 为什么每个质数都有原根

每个质数 $p$ 都存在原根。 $p = 2$ 时唯一非零类1就是原根，以下讨论 $p > 2$ 。这个结论的关键是：在模质数的运算中，一个非零多项式的根数不超过它的次数。因此，所有非零余数不可能都过早回到1。

具体说，令 $N = p - 1$ ，固定 $N$ 的一个质数幂因子 $ℓ^{e}$ ，其中 $ℓ^{e + 1}$ 不再整除 $N$ 。多项式 $X^{N / ℓ} - 1$ 的次数是 $N / ℓ < N$ ，不可能让全部 $N$ 个非零余数都成为根。因此存在一个余数 $a$ 满足 $a^{N / ℓ} ≢ 1$ 。

$a$ 的阶 $d$ 整除 $N$ ，但不整除 $N / ℓ$ 。所以 $d$ 中必须含有完整的因子 $ℓ^{e}$ ；否则它的每个质数幂因子都包含在 $N / ℓ$ 里，就会整除 $N / ℓ$ 。具体取 $b = a^{d / ℓ^{e}}$ ；幂阶公式给出它的阶为 $d / gcd (d, d / ℓ^{e}) = ℓ^{e}$ ，因此我们得到一个阶恰为 $ℓ^{e}$ 的元素。

对 $N$ 的每个不同质因子这样做，得到一组阶两两互质的元素。在交换群中，阶互质的两个元素相乘，其阶等于两阶的乘积。逐个相乘，就得到阶为 $N$ 的元素，也就是原根。

这里用到的多项式根数结论、幂阶公式以及“阶互质则乘积阶相乘”，在第14章逐项完整证明。这一段说明它们怎样接起来，避免把原根存在当作未经解释的口号。

5.4 为什么原根有欧拉函数那么多个

固定一个原根 $g$ ，令 $N = p - 1$ 。全部非零类是 $g^{k}$ ，且第4.4节给出

{ord}_{p} (g^{k}) = \frac{N}{gcd (N, k)} .

所以 $g^{k}$ 仍为原根，当且仅当 $gcd (N, k) = 1$ 。在 $0 \leq k < N$ 的编号中，符合条件的个数就是 $φ (N)$ 。因此模 $p$ 原根的个数为 $φ (p - 1)$ ； $p = 2$ 时只有非零类1，数量也是 $φ (1) = 1$ 。

合数模数下不能直接沿用原根存在性。例如模8的可逆类 $1, 3, 5, 7$ 都平方为1，任何一个元素的阶都不超过2，无法生成4个元素。第14章也解释为什么多项式的根数论证不能照搬到一般合数模数。

第 6 章：中国剩余定理与余数坐标

返回目录

6.1 定理怎样合并多个同余条件

设 $m_{1}, \dots, m_{k}$ 是两两互质的正整数， $M = m_{1} \dots m_{k}$ 。中国剩余定理（CRT）说：给定任意余数 $a_{1}, \dots, a_{k}$ ，同余组

x \equiv a_{i} (\mod m_{i}) (1 \leq i \leq k)

有解，而且模 $M$ 只有一个解。也就是说，答案可以有很多个整数代表，但它们都相差 $M$ 的倍数。

“两两互质”是每一对不同模数的最大公约数都为1。它使各个同余要求之间没有共同因子造成的冲突，也保证完整周期是乘积 $M$ 。

6.2 为什么存在：构造只影响一个坐标的项

令 $M_{i} = M / m_{i}$ 。由于模数两两互质， $M_{i}$ 与 $m_{i}$ 互质，所以有逆元 $t_{i}$ 满足 $M_{i} t_{i} \equiv 1 (\mod m_{i})$ 。

现在看 $E_{i} = M_{i} t_{i}$ ：它对 $m_{i}$ 余1，对所有其他 $m_{j}$ 余0，因为 $M_{i}$ 含有 $m_{j}$ 这个因子。于是

x = \sum_{i = 1}^{k} a_{i} E_{i}

对 $m_{j}$ 取模时，除第 $j$ 项以外都消失，只留下 $a_{j} \cdot 1$ 。所以这个 $x$ 同时满足全部要求。这不是单纯记一个求和公式，而是在构造“只负责一个余数条件”的项，再把它们相加。

6.3 为什么唯一，以及为什么可以使用两个坐标

若 $x, y$ 都满足全部同余，所有 $m_{i}$ 都整除 $x - y$ 。因为 $m_{i}$ 两两互质，它们的乘积 $M$ 也整除 $x - y$ ，即 $x \equiv y (\mod M)$ 。这就证明模 $M$ 的唯一性。

特别地，若 $p, q$ 是不同质数，模 $n = p q$ 的每个剩余类都唯一对应一对坐标：

x mod n ⟷ (x mod p, x mod q) .

任意一对坐标都能合起来，合起来的类又只有一个，这就是双射。加法、乘法、取幂都可以在两个坐标分别进行，再合并结果。

例如模55的34对应 $(4, 1)$ ，也就是模5为 $- 1$ 、模11为1。计算 $34^{2}$ 时，两边分别平方都得到1，CRT就保证 $34^{2} \equiv 1 (\mod 55)$ 。这个例子只用于展示坐标的含义；一般结论是上面的双射。

如果 $x$ 与 $p q$ 互质，两个坐标都非零；反过来，两坐标都非零也意味着 $x$ 与 $p q$ 互质。因此CRT还给出 $U_{p q} ⟷ U_{p} \times U_{q}$ 。第9章会用它解释随机底数为什么产生独立坐标。

6.4 模数不互质时怎样修改

对于 $x \equiv a (\mod m)$ 、 $x \equiv b (\mod n)$ ，若 $m, n$ 不互质，两个要求可能冲突。正确的相容条件是

gcd (m, n) ∣ (b - a) .

必要性很直接： $x - a$ 被 $m$ 整除， $x - b$ 被 $n$ 整除，所以二者都被最大公约数整除，相减得到 $b - a$ 也必须被它整除。

充分性可由线性同余看出。令 $c = gcd (m, n)$ ，先写 $x = a + m k$ ，代入第二个条件得到 $m k \equiv b - a (\mod n)$ 。若 $c ∣ (b - a)$ ，把整除关系中的三项都除以 $c$ ，就得到模 $n / c$ 的同余； $m / c$ 与 $n / c$ 互质，可以用逆元解出 $k$ 。解的周期是 $lcm (m, n) = m n / c$ ，这里 $lcm$ 表示最小公倍数。

多个模数的情形有解，当且仅当每一对余数满足对应的相容条件；最终周期是所有模数的最小公倍数。两两相容为什么足够，以及完整构造与唯一性证明，均放在第13章。

第 7 章：RSA的指数选择与解密正确性

返回目录

7.1 公钥、私钥和模数各自做什么

取两个不同的奇质数 $p, q$ ，令 $n = p q$ 。消息 $m$ 用模 $n$ 的一个剩余类表示。公钥是 $(n, e)$ ，加密把 $m$ 变为 $c \equiv m^{e} (\mod n)$ ；私钥指数 $d$ 用于计算 $c^{d} (\mod n)$ 。

要让解密回到 $m$ ，需要安排 $(m^{e})^{d} = m^{e d}$ 与 $m$ 同余。做法是选择 $e, d$ 满足

e d \equiv 1 (\mod φ (n)), φ (n) = (p - 1) (q - 1) .

于是存在非负整数 $h$ 使 $e d = 1 + h φ (n)$ 。两个指数相乘后的“多余部分”是欧拉指数的倍数，这是它与欧拉定理连接的地方。

7.2 这些指数为什么一定可以选出来

先计算 $φ (n)$ ，再选择与它互质的正整数 $e$ 。由第1章的逆元条件， $e$ 模 $φ (n)$ 有逆元 $d$ ，可以用扩展欧几里得算法算出，并取一个正整数代表。

因此 $e, d$ 并非任意设定后再假定它们满足关系；先选择互质的 $e$ ，逆元定理保证 $d$ 存在。这里逆元的模数是 $φ (n)$ ，加密时的模数是 $n$ ，两者用途不同。

对于与 $n$ 互质的消息，欧拉定理直接给出

m^{e d} = m^{1 + h φ (n)} = m (m^{φ (n)})^{h} \equiv m (\mod n) .

但这只处理了互质消息。若消息含有 $p$ 或 $q$ 这个因子，不能继续套用模 $n$ 的欧拉定理；需要下面的逐质数证明。

7.3 不互质的消息为什么也能还原

先对 $p$ 证明 $m^{e d} \equiv m$ ，分成两个互补的情况。

若 $p ∣ m$ ，因为 $e d \geq 1$ ， $m^{e d}$ 和 $m$ 模 $p$ 都为0。若 $p ∤ m$ ，可以用费马小定理 $m^{p - 1} \equiv 1 (\mod p)$ 。而 $p - 1$ 整除 $φ (n)$ ，故也整除 $e d - 1$ ，于是

m^{e d} = m (m^{p - 1})^{(e d - 1) / (p - 1)} \equiv m (\mod p) .

无论 $p$ 是否整除消息，模 $p$ 的结论都成立。对 $q$ 完全同理，得到 $m^{e d} \equiv m (\mod q)$ 。CRT再把两个结论合起来，得到 $m^{e d} \equiv m (\mod n)$ 。

这份证明没有假设消息与 $n$ 互质。它利用的是：在每个质数坐标上，消息要么为0，要么可用费马小定理；两种情况覆盖了全部消息。

7.4 这与分解有什么关系

若能分解 $n$ 得到 $p, q$ ，就能计算 $φ (n)$ ，再由公开的 $e$ 计算逆元 $d$ ，从而解密。这证明了

分解 n ⟹ 恢复私钥指数并解密 .

还可以追问：已知 $d$ ，能不能反过来分解 $n$ ？答案是可以使用随机算法；下一章从 $e d - 1$ 出发说明为什么。

这里讨论RSA的数学幂运算。实际RSA参数可采用更弱的 $e d \equiv 1 (\mod λ (n))$ 条件，其中 $λ (n) = lcm (p - 1, q - 1)$ ；它仍足以完成上面的逐质数证明。统一指数与具体规范的关系放在第16章。标准依据见RFC 8017第3.2节。

第 8 章：已知私钥怎样随机分解模数

返回目录

8.1 私钥给了我们哪一条额外信息

沿用 $n = p q$ ，其中 $p, q$ 为不同奇质数。原对话的私钥关系给出

K = e d - 1 > 0, φ (n) ∣ K .

对于任意与 $n$ 互质的 $a$ ，欧拉定理保证 $a^{K} \equiv 1 (\mod n)$ 。我们知道 $n, e, d$ ，所以能计算 $K$ ；这一步并不要求知道 $p, q$ 。证明中使用 $p, q$ 解释算法，算法本身不能预先使用它们。

把 $K$ 中的全部因子2提出，写成 $K = 2^{s} r$ ，其中 $r$ 为奇数。由于 $φ (n)$ 是偶数，这里 $s \geq 1$ 。接着构造连续平方序列

x_{0} = a^{r} mod n, x_{j + 1} = x_{j}^{2} mod n .

第 $j$ 项同余于 $a^{2^{j} r}$ ，因此终点 $x_{s} \equiv a^{K} \equiv 1$ 。我们不是盲目平方；终点已由指数条件保证，现在要研究第一次到1之前的一项。

8.2 为什么“平方为1”能产生因子

若某个 $x$ 满足 $x^{2} \equiv 1 (\mod n)$ ，则 $n ∣ (x - 1) (x + 1)$ 。模 $p$ 看， $p$ 是质数，所以 $p$ 必须整除 $x - 1$ 或 $x + 1$ ，即 $x \equiv 1$ 或 $- 1 (\mod p)$ 。模 $q$ 同理。

因此 $x$ 的两个CRT坐标只能是下面四种组合：

模 $p$	模 $q$	合并后的意义
$1$	$1$	$x \equiv 1 (\mod n)$
$- 1$	$- 1$	$x \equiv - 1 (\mod n)$
$1$	$- 1$	两边符号不同
$- 1$	$1$	两边符号不同

CRT保证每种组合对应一个根。因为 $p, q$ 都为奇数，模各个质数的1与 $- 1$ 不同，所以这四个根也互不相同。

最后两种称为1的非平凡平方根。若 $x \equiv 1 (\mod p)$ 、 $x \equiv - 1 (\mod q)$ ，那么 $p ∣ x - 1$ ，但 $q ∤ x - 1$ ；否则 $q$ 会同时整除 $x - 1$ 与 $x + 1$ ，进而整除它们的差2，与 $q$ 为奇质数矛盾。因此

gcd (x - 1, n) = p, gcd (x + 1, n) = q .

符号相反时两个因子互换。最大公约数提取因子，是因为两个质因子分别落在 $x - 1$ 和 $x + 1$ 中，不是仅凭“平方为1”就能分解。若 $x \equiv \pm 1 (\mod n)$ ，得到的只是1或整个 $n$ ，没有拆出因子。

8.3 第一次到1之前的一项为什么值得检查

假设 $x_{0} \neq 1$ ，并设 $x_{j}$ 是序列第一次出现的1，那么 $j \geq 1$ 。它的前一项 $x_{j - 1}$ 满足 $x_{j - 1}^{2} \equiv 1$ ，但 $x_{j - 1} ≢ 1$ ，因为这是第一次到1。

所以前一项只剩两种可能：它等于 $- 1$ ，算法这次失败；或者它是非平凡平方根，可以提取因子。初始就为1时也失败，因为没有前一项可检查。

一个简短核对是 $n = 55, e = 3, d = 27$ ，从而 $K = 80 = 2^{4} \cdot 5$ 。取 $a = 2$ ，初始项 $2^{5} \equiv 32$ ，随后平方得到 $34$ 、1。前一项34不是1或54，所以得到 $gcd (33, 55) = 11$ 。它只是一般算法的一次实例；成功条件来自上一节的四种符号组合。

8.4 完整算法与失败分支

算法可以写成下面的顺序。所有余数均取 $0$ 至 $n - 1$ 的代表，输入满足上面的指数条件。

从 $1, \dots, n - 1$ 均匀选取 $a$ ，计算 $g = gcd (a, n)$ 。若 $g > 1$ ，因 $a < n$ ， $g$ 已是一个真因子，输出 $g, n / g$ 。
若 $g = 1$ ，计算 $x = a^{r} mod n$ 。若 $x = 1$ ，本次失败，重新独立选取底数。
最多进行 $s$ 轮：令 $y = x^{2} mod n$ 。若 $y \neq 1$ ，令 $x = y$ 继续；若 $y = 1$ 且 $x = n - 1$ ，本次失败；若 $y = 1$ 且 $x \neq n - 1$ ，输出 $gcd (x - 1, n)$ 及另一个因子。

最后一个分支里的 $x$ 也不可能是1：初始为1的情况已排除，后续一出现1就终止。因此它确实是非平凡平方根。合法输入下一定能在 $s$ 轮内到达1，因为 $x_{s} = a^{K} \equiv 1$ 。输出因子可以用乘法检查。

8.5 为什么还需要证明概率

我们已经证明：若遇到非平凡平方根，算法会成功；也说明它可能失败。尚未证明的是，随机选择底数会多频繁地产生有用的根。

不能仅凭“四个平方根有两个有用”就断言成功率为一半。连续平方产生四个根的概率未必相同。需要从随机底数 $a$ 出发，分析算法实际到达哪一个根。接下来的三章完成这一步。

第 9 章：成功条件与两个首次到达时间

返回目录

9.1 先固定随机选择的范围

先只研究与 $n$ 互质的底数，即从 $U_{n}$ 中均匀选取 $a$ 。均匀表示其中每个剩余类被选到的概率都为 $1 / φ (n)$ 。一旦 $a$ 选定，后续取幂、平方和取最大公约数都由它确定，没有新的随机选择。

第8章从全部 $1, \dots, n - 1$ 抽样的算法也适用：不互质的底数直接给出因子；条件于“选到的 $a$ 互质”，各个互质底数仍然等可能。因此先证明互质分支的成功率，再把直接成功的分支加回来即可。

9.2 为什么要定义两个到达时间

连续平方的第 $j$ 项是 $x_{j} \equiv a^{2^{j} r} (\mod n)$ 。用CRT拆开，模 $p$ 和模 $q$ 各自形成一条平方序列。两边都最终到1，但到达的时刻可能不同。

令

T_{p} = min {j \geq 0 : a^{2^{j} r} \equiv 1 (\mod p)}, T_{q} = min {j \geq 0 : a^{2^{j} r} \equiv 1 (\mod q)} .

$T_{p}$ 表示模 $p$ 第一次到1时，已经做了多少次平方； $T_{q}$ 含义相同。初始 $a^{r}$ 已经为1时，次数记为0。这两个量都由随机底数 $a$ 决定，因此称为随机变量。它们存在且不大于 $s$ ，因为第 $s$ 项已经为1；到1以后再平方，仍为1。

引入它们的目的，是把“前一项属于哪种平方根”转化为“两个坐标是否同时第一次到1”。后者更容易计数。

9.3 为什么到达时间不同就成功

设 $T_{p} < T_{q}$ 。整体序列第一次到1的时刻是 $T_{q}$ ：此时两边都为1，而此前模 $q$ 还未到1。考察前一项 $j = T_{q} - 1$ 。

模 $p$ 已经到1，所以前一项的 $p$ 坐标为1。模 $q$ 尚未到1，但下一次平方将为1，所以前一项的 $q$ 坐标是 $- 1$ 。这里用的是质数下方程 $x^{2} = 1$ 只有 $\pm 1$ 两个根，排除1后就只剩 $- 1$ 。

因此前一项的坐标为 $(1, - 1)$ ，是非平凡平方根，算法成功。若 $T_{q} < T_{p}$ ，同理得到 $(- 1, 1)$ ，也成功。

若 $T_{p} = T_{q} = t > 0$ ，前一项的两边都尚未到1，下一次却都为1，所以前一项为 $(- 1, - 1)$ ，即整体的 $- 1$ ，算法失败。若 $t = 0$ ，初始整体已为1，也失败。所有可能都已覆盖，因此对于互质底数，

成功 ⟺ T_{p} \neq T_{q}, 失败 ⟺ T_{p} = T_{q} .

这一步只解释成功与失败的条件，还没有给出概率。下一步要问两个到达时间分别怎样分布，以及它们是否独立。

9.4 CRT为什么给出独立的随机坐标

第6章给出双射 $U_{n} ⟷ U_{p} \times U_{q}$ 。右边共有 $(p - 1) (q - 1)$ 对坐标；每一对恰好对应一个底数。均匀选择 $U_{n}$ 中的底数，就等价于等可能地选择这些坐标对。

记 $A_{p} = a mod p$ 、 $A_{q} = a mod q$ 。固定一个非零余数 $b$ 和一个非零余数 $c$ ，有

P (A_{p} = b, A_{q} = c) = \frac{1}{(p - 1) (q - 1)} .

固定 $b$ 而让 $c$ 任意，一共有 $q - 1$ 对，所以 $P (A_{p} = b) = 1 / (p - 1)$ ；同理 $P (A_{q} = c) = 1 / (q - 1)$ 。联合概率等于两个边缘概率的乘积，这正是独立性。

也可以把坐标对看成一个完整的行列表：模 $p$ 余数决定行，模 $q$ 余数决定列。知道选中了哪一行，仍不会偏向这行中的某一列，因为每行都有相同的全部列。这个理解对应的仍是上面的精确计数，而不是另外的假设。

9.5 同一个底数产生的两个到达时间为什么也独立

$T_{p}$ 只需要 $a$ 的 $p$ 坐标就能计算， $T_{q}$ 只需要 $q$ 坐标；固定的 $r$ 没有额外随机性。因此分别对两个独立坐标做确定的运算，不会让它们相关。

把这一点写成计数更清楚。令 $B_{t}$ 为模 $p$ 到达时间等于 $t$ 的余数集合， $C_{u}$ 为模 $q$ 到达时间等于 $u$ 的余数集合。事件 $T_{p} = t, T_{q} = u$ 对应 $B_{t} \times C_{u}$ ，所以

P (T_{p} = t, T_{q} = u) = \frac{| B_{t} | | C_{u} |}{(p - 1) (q - 1)} = P (T_{p} = t) P (T_{q} = u) .

这里 $| B_{t} |$ 表示集合中的元素个数。对任意 $t, u$ 都成立，所以 $T_{p}, T_{q}$ 独立。关键不是“它们来自同一个底数”或“它们来自两个质数”，而是CRT保证均匀底数对应完整、均匀的坐标对。

9.6 概率证明现在还缺哪一步

我们已把失败转化为 $T_{p} = T_{q}$ ，也证明了两者独立。还需要知道：每个到达时间出现的概率是否有统一上界。

接下来的目标是证明，对于任意 $t$ ， $P (T_{p} = t) \leq 1 / 2$ ，模 $q$ 也一样。路线是：先证明取幂后的初始余数在一个较小循环群上均匀，再根据元素的阶统计首次到达时间。这里“元素均匀”与“到达时间均匀”是不同结论；后一种均匀实际上通常不成立。

第 10 章：取幂的均匀性与到达时间分布

返回目录

10.1 均匀输入怎样才能产生均匀输出

先说明一个将反复使用的计数原则。若 $X$ 在一个有限集合 $S$ 上均匀，令 $Y = f (X)$ 。对于一个输出 $y$ ，

P (Y = y) = \frac{| {x \in S : f (x) = y} |}{| S |} .

分子是产生 $y$ 的输入个数，也称 $y$ 的原像个数。因为每个输入概率相同，输出概率就由有多少个输入合到这里决定。若每个可能输出的原像一样多，输出才均匀；若 $f$ 是双射，每个输出只有一个原像，当然也均匀。

所以“底数均匀”本身不足以推出“取幂后均匀”。下面必须实际检查这个取幂映射的原像数量，以及哪些映射是双射。

10.2 把模数的乘法周期拆成奇部和2的幂

只分析模 $p$ ，模 $q$ 同理。把 $p - 1$ 中的因子2全部提出，写成

p - 1 = 2^{α} u, u 为奇数 .

$α$ 表示 $p - 1$ 含有多少个因子2；因为 $p$ 为奇质数， $α \geq 1$ 。另一方面，算法的指数是 $K = 2^{s} r$ ， $r$ 为奇数。由于 $p - 1 ∣ K$ ，有 $s \geq α$ 和 $u ∣ r$ 。

后一个整除关系为什么成立？ $u ∣ 2^{s} r$ ，但 $u$ 是奇数，与 $2^{s}$ 互质，所以可以消去 $2^{s}$ ，推出 $u ∣ r$ 。于是写 $r = u w$ ， $w$ 也为奇数。

取模 $p$ 的原根 $g$ ，令 $h = g^{u}$ 。因为 $g$ 的阶为 $p - 1 = 2^{α} u$ ，第4.4节给出

{ord}_{p} (h) = \frac{2^{α} u}{gcd (2^{α} u, u)} = 2^{α} .

因此 $h$ 生成一个恰有 $2^{α}$ 个元素的循环群

H_{p} = {1, h, h^{2}, \dots, h^{2^{α} - 1}} (mod p) .

提出奇部 $u$ 的作用，就是从长度 $2^{α} u$ 的原根循环中，得到长度纯为2的幂的循环。算法先算 $a^{r}$ ，也会消去这个奇部；下一节把两件事连接起来。

10.3 为什么指数开始对2的幂取模

原根给出唯一编号 $a \equiv g^{k} (\mod p)$ ，其中 $0 \leq k < 2^{α} u$ 。取 $r = u w$ 次幂后，

a^{r} \equiv (g^{k})^{u w} = (g^{u})^{k w} = h^{k w} (\mod p) .

现在底数变为 $h$ ，它的阶是 $2^{α}$ 。所以 $h^{k w}$ 的值由指数 $k w mod 2^{α}$ 决定。这就是为什么指数的模数变为 $2^{α}$ 。

幂值仍在模 $p$ 下计算，指数则按 $h$ 的周期取模 $2^{α}$ 。 没有把 $a^{r} mod p$ 改成 $a^{r} mod 2^{α}$ 。第4.3节的指数与幂值区分在这里再次出现。

10.4 为什么取幂后在这个循环群上均匀

由第9章， $a mod p$ 在全部非零类上均匀。原根编号是双射，所以 $k$ 也在 $0, \dots, 2^{α} u - 1$ 上均匀。接着沿上一节的等式分三步看分布。

首先将 $k$ 对 $2^{α}$ 取余。固定余数 $j$ ，恰有

j, j + 2^{α}, \dots, j + (u - 1) 2^{α}

这 $u$ 个编号产生它。每个余数的原像数相同，所以 $k mod 2^{α}$ 均匀，每个概率为 $u / (2^{α} u) = 2^{- α}$ 。

其次把这个余数乘 $w$ 。因为 $w$ 为奇数， $gcd (w, 2^{α}) = 1$ ，乘法可消去：若 $w j_{1} \equiv w j_{2} (\mod 2^{α})$ ，必有 $j_{1} \equiv j_{2}$ 。因此乘 $w$ 是一个排列， $k w mod 2^{α}$ 仍均匀。此处只需要 $w$ 与 $2^{α}$ 互质，不需要它与整个 $p - 1$ 互质。

最后由编号 $j$ 转为 $h^{j} mod p$ 。由于 $h$ 的阶恰好为 $2^{α}$ ，这又是双射。所以

a^{r} mod p 在 H_{p} 上均匀，每个元素的概率为 2^{- α} .

完整的依据依次是：原根给出双射编号，取余有等大小原像，乘奇数是排列，最后的幂编号又是双射。 取幂通常没有在全部 $p - 1$ 个非零类上保持均匀，而是在这个较小的 $H_{p}$ 上均匀。

如果希望核对各步，可以取 $p = 13$ ： $p - 1 = 4 \cdot 3$ ，选原根 $g = 2$ ，则 $h = 8$ 的阶为4。取 $r = 9$ ，有 $w = 3$ ；12个编号对4取余时每个余数有3个原像，乘3再把四个余数重排，因此输出 $1, 8, 12, 5$ 各占 $1 / 4$ 。这个例子对应上面的原像数与排列，不承担一般证明。

10.5 到达时间为什么由元素阶决定

令 $z = a^{r} mod p$ ，它已在 $H_{p}$ 中。假设 $z$ 的阶为 $d$ 。连续平方 $j$ 次就是计算 $z^{2^{j}}$ ，所以第4.2节告诉我们

z^{2^{j}} \equiv 1 (\mod p) ⟺ d ∣ 2^{j} .

因为 $H_{p}$ 是 $2^{α}$ 阶循环群， $z$ 的阶必为 $2^{t}$ ，其中 $0 \leq t \leq α$ 。这可以直接从 $z = h^{k}$ 与幂阶公式 $d = 2^{α} / gcd (2^{α}, k)$ 看出，也符合“元素阶整除群阶”的一般定理。

当 $d = 2^{t}$ 时， $d ∣ 2^{j}$ 等价于 $j \geq t$ ，所以最早到1的时刻恰为 $T_{p} = t$ 。 $t = 0$ 意味着 $d = 1$ ，即初始 $z$ 已经是1。现在问题变成： $H_{p}$ 中有多少个元素的阶恰为 $2^{t}$ ？

10.6 怎样从阶的个数得到概率

先做一般计数。设 $h$ 的阶为 $N$ ，全部元素是 $h^{k}$ ， $0 \leq k < N$ 。若 $d ∣ N$ ，由幂阶公式， $h^{k}$ 的阶恰好为 $d$ 等价于

gcd (N, k) = \frac{N}{d} .

满足条件的编号必能写成 $k = (N / d) j$ ，其中 $0 \leq j < d$ 。代入最大公约数，条件进一步等价于 $gcd (d, j) = 1$ 。这样的 $j$ 恰有 $φ (d)$ 个，所以循环群中阶恰为 $d$ 的元素有 $φ (d)$ 个。 $d = 1$ 时只有单位元；第15章保留完整的群论证明。

回到 $N = 2^{α}$ 。阶为1的元素有1个；阶为 $2^{t}$ 、 $1 \leq t \leq α$ 的元素有 $φ (2^{t}) = 2^{t - 1}$ 个。这是因为 $0$ 至 $2^{t} - 1$ 中与 $2^{t}$ 互质的编号正是奇数，恰占一半。

每个元素的概率已知为 $2^{- α}$ ，因此

P (T_{p} = t) = {\begin{cases} 2^{- α}, & t = 0, \\ 2^{t - 1 - α}, & 1 \leq t \leq α, \\ 0, & 其他整数 t . \end{cases}

这是“符合条件的元素个数除以全部元素个数”，不是把各个到达时间直接设成等可能。比如 $α = 2$ 时，阶1、2、4分别有1、1、2个元素，所以 $T_{p}$ 取0、1、2的概率为 $1 / 4, 1 / 4, 1 / 2$ 。这个小例子显示：元素均匀，到达时间却不均匀，因为不同阶的元素数量不同。

一般情况下，所有概率的总和为 $(1 + 1 + 2 + \dots + 2^{α - 1}) / 2^{α} = 1$ 。而每个概率都不超过 $1 / 2$ ： $t = 0$ 用 $α \geq 1$ ； $1 \leq t \leq α$ 时最大值在 $t = α$ 取得，恰为 $2^{α - 1} / 2^{α} = 1 / 2$ 。模 $q$ 完全同理，只需把 $α$ 换成 $q - 1$ 中因子2的次数 $β$ 。

第 11 章：相等概率为什么是加权平均

返回目录

11.1 相等事件怎样分成互不重叠的情况

已知 $T_{p}, T_{q}$ 独立，且 $T_{q}$ 取任意具体值的概率都不超过 $1 / 2$ 。要计算 $T_{p} = T_{q}$ ，需要考虑它们可能同时等于0、同时等于1，等等。

不同共同取值对应互不重叠的事件：一次选择不可能既使两者同时等于0，又使它们同时等于1。因此可以把这些概率相加。独立性允许把每个“同时发生”的概率拆成乘积，于是

P (T_{p} = T_{q}) = \sum_{t} P (T_{p} = t, T_{q} = t) = \sum_{t} P (T_{p} = t) P (T_{q} = t) .

求和覆盖所有可能的整数 $t$ ；范围之外的概率为0。这里有两个不同理由：能相加，是因为共同取值的情况互不重叠；能相乘，是因为两个随机变量独立。不能把二者合并成一句“概率相加相乘”。

11.2 为什么不是把多个二分之一直接相加

令 $a_{t} = P (T_{p} = t)$ 、 $b_{t} = P (T_{q} = t)$ 。第一个概率 $a_{t}$ 是“ $T_{p}$ 取这个值”的比例，第二个概率 $b_{t}$ 是这个值出现后，独立的 $T_{q}$ 恰好匹配它的概率。

因此 $a_{t} b_{t}$ 才是这一种匹配在所有情况中所占的比例。只加 $b_{t}$ ，就忽略了 $T_{p}$ 取各个值的机会不同；把每一类内部的匹配率都当成全部情况的匹配率，也就不再是在算原来的事件。

这里 $a_{t} \geq 0$ 且 $\sum_{t} a_{t} = 1$ ，因为 $T_{p}$ 总会取它的某一个可能值。因此 $\sum_{t} a_{t} b_{t}$ 是以 $a_{t}$ 为权重，对 $b_{t}$ 取加权平均。权重总和为1，是后面上界能保持为 $1 / 2$ 的关键。

11.3 一个短例子区分实际值与上界

用你补充过的分布核对这句话：若 $a_{t}$ 依次为 $1 / 4, 1 / 4, 1 / 2$ ，而 $b_{t}$ 为 $1 / 2, 1 / 2, 0$ ，实际相等概率是

\frac{1}{4} \cdot \frac{1}{2} + \frac{1}{4} \cdot \frac{1}{2} + \frac{1}{2} \cdot 0 = \frac{1}{4} .

只知道每个 $b_{t} \leq 1 / 2$ 时，可以把每一项的 $b_{t}$ 替换成更大的上界 $1 / 2$ ，得到

P (T_{p} = T_{q}) \leq \frac{1}{4} \cdot \frac{1}{2} + \frac{1}{4} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = (\frac{1}{4} + \frac{1}{4} + \frac{1}{2}) \frac{1}{2} = \frac{1}{2} .

第三个实际匹配率0被放宽成 $1 / 2$ ，所以实际值 $1 / 4$ 与通用上界 $1 / 2$ 可以同时成立。这里真正发挥作用的是三个权重加起来为1，而不是只有三个可能取值。下一节不再依赖这些具体比例。

11.4 一般情况下，上界为什么不会被求和放大

对每一个 $t$ ，由于 $a_{t} \geq 0$ 且 $b_{t} \leq 1 / 2$ ，都有 $a_{t} b_{t} \leq a_{t} / 2$ 。逐项相加，得到

\begin{aligned} P (T_{p} = T_{q}) & = \sum_{t} a_{t} b_{t} \\ \leq \sum_{t} a_{t} \cdot \frac{1}{2} \\ = \frac{1}{2} \sum_{t} a_{t} \\ = \frac{1}{2} . \end{aligned}

第二行使用每一项的上界，第三行只把公共常数 $1 / 2$ 提出求和，第四行使用权重总和为1。可能取值更多，并不会改变最后一步；增加一个可能值，也意味着要在总和为1的权重中分给它一部分。

这就是一般原则：若 $a_{t} \geq 0$ 、 $\sum_{t} a_{t} = 1$ ，且每个 $b_{t} \leq M$ ，那么 $\sum_{t} a_{t} b_{t} \leq M$ 。加权平均不会超过参与平均的各个值的最大值。

11.5 条件概率怎样解释同一个推导

全概率公式把相等事件按 $T_{p}$ 的取值分类：

P (T_{p} = T_{q}) = \sum_{t : P (T_{p} = t) > 0} P (T_{p} = t) P (T_{q} = t ∣ T_{p} = t) .

条件概率 $P (T_{q} = t ∣ T_{p} = t)$ 表示：已知 $T_{p} = t$ 后， $T_{q}$ 恰好匹配它的概率。由于独立，已知 $T_{p}$ 不会改变 $T_{q}$ 的分布，所以这个条件概率等于 $P (T_{q} = t) \leq 1 / 2$ 。将这些匹配概率按 $T_{p}$ 各值出现的比例平均，总匹配概率仍不超过 $1 / 2$ 。

独立性为什么不能省略？如果 $X$ 等可能取0、1，再令 $Y = X$ ，那么 $Y$ 取每个值的概率都为 $1 / 2$ ，但 $P (X = Y) = 1$ 。原因是知道 $X$ 以后， $Y$ 的匹配概率变成1。RSA这里没有这个问题，因为第9章已经用CRT证明了两个坐标以及分别由它们决定的到达时间独立。

11.6 怎样得到至少一半的成功概率

第9章证明，对于互质底数，成功恰好是 $T_{p} \neq T_{q}$ 。相等与不相等互为补集，所以

P (成功) = 1 - P (T_{p} = T_{q}) \geq \frac{1}{2} .

把全部推理连起来：CRT提供独立坐标 → 取幂后在2的幂阶循环群上均匀 → 按元素阶统计到达时间 → 每个到达时间概率不超过一半 → 相等概率是加权平均 → 失败概率不超过一半。各步分别在第9—11章证明；最后一步没有省去前面条件。

结论适用于两个不同奇质数的乘积 $n = p q$ 、正整数 $K$ 满足 $p - 1, q - 1 ∣ K$ 、从全部互质类均匀抽样。原对话使用的 $K = e d - 1$ 且 $φ (n) ∣ K$ 满足这些条件； $λ (n) ∣ K$ 也足够。

若从全部 $1, \dots, n - 1$ 抽样，不互质底数直接成功，互质部分的条件分布仍均匀。因此完整一次尝试也至少有一半成功率。更精确地，若 $ρ$ 是互质分支的成功率，则

P (完整尝试成功) = 1 - \frac{φ (n)}{n - 1} (1 - ρ) \geq \frac{1}{2} .

这里 $φ (n) / (n - 1)$ 是进入互质分支的概率；只有这一分支内的失败可能保留下来。精确概率公式在第16章，理解这条下界不必先算出它。

第 12 章：重试、运行时间与RSA结论的范围

返回目录

12.1 失败以后重试为什么有效

每次失败后重新独立、均匀选择底数，就得到新的一次尝试。若每次失败概率至多 $1 / 2$ ，独立重复 $k$ 次都失败的概率至多

{(\frac{1}{2})}^{k} = 2^{- k} .

“独立重复”不能省略。若一直重复同一个失败底数，后续计算完全一样，重复次数增加不会改善成功率。重新抽样让前一次的失败不改变下一次的分布。

算法输出的因子始终可以验证，因此随机性影响的是需要尝试多少次，不影响成功输出是否正确。有限次全失败时，可以继续尝试；它不构成错误的分解结果。

12.2 为什么平均至多两次，不等于两次必成功

设单次成功率为 $ρ \geq 1 / 2$ ，令 $N$ 为第一次成功时的尝试总次数。第 $k$ 次恰好第一次成功，需要前 $k - 1$ 次失败、第 $k$ 次成功，所以 $P (N = k) = (1 - ρ)^{k - 1} ρ$ 。

期望 $E [N]$ 表示大量独立运行中尝试次数的平均值。其值为 $1 / ρ \leq 2$ 。这个求和也可以从“第 $j + 1$ 轮是否需要做”理解：第1轮一定需要做，第2轮只有第一次失败才需要做，第3轮只有前两次都失败才需要做。因此

E [N] = \sum_{j = 0}^{\infty} P (N > j) = \sum_{j = 0}^{\infty} (1 - ρ)^{j} = \frac{1}{ρ} \leq 2.

第一等式的依据是：一个恰做 $k$ 轮的运行，会在 $N > 0, N > 1, \dots, N > k - 1$ 这 $k$ 个条件中各被计一次。对这些轮次指标取平均，再相加，就是平均总轮数。这解释了为什么能用尾概率计算期望。

期望至多2是平均表现，不是每次最多2轮；做很多轮仍有可能，只是尾概率按几何速度减小。

12.3 为什么是期望多项式时间

每次尝试需要求最大公约数、计算 $a^{r} mod n$ 以及最多 $s$ 次平方。快速幂按照 $r$ 的二进制展开进行，使用 $O (\log r)$ 次模乘法； $s \leq \log_{2} K$ ，所以一次尝试的运算次数是 $O (\log K)$ 量级。

再考虑每个整数运算的位复杂度：中间余数小于 $n$ ，有 $O (\log n)$ 位；模乘法与欧几里得算法都有关于这些位长的多项式时间实现。因此单轮耗时是关于 $\log n, \log K$ 的多项式。期望轮数至多2，所以期望总耗时仍为多项式。

“多项式时间”是按输入的位数衡量，不是按 $n$ 本身衡量。完整位复杂度说明保留在第16章；本节说明成功概率怎样与运行时间接起来。标准结论的依据见《Handbook of Applied Cryptography》第3章Fact 3.30及第8章Fact 8.6。

12.4 恢复私钥与从密文恢复消息为什么要区分

我们证明了两个方向：分解 $n$ 可以恢复 $d$ ；已知满足条件的私钥指数 $d$ ，可以随机分解 $n$ 。因此“恢复私钥指数”与“分解模数”具有这里证明的计算联系。

但给定 $(n, e, c)$ ，直接求出满足 $m^{e} \equiv c (\mod n)$ 的消息，是另一种已知信息和计算任务。能还原一个密文，并不意味着已经得到一个对所有消息适用的私钥指数 $d$ 。上面的随机分解算法必须从 $d$ 构造已知的 $K = e d - 1$ ，不能从“某条消息已还原”自动得到这个输入。

所以这里没有证明“任意解密能力都能用于分解”。即便一种方法确实会解密，也不能把分解算法需要的私钥信息直接当作它已经提供的信息。RSA求逆与整数分解之间的这个逻辑区别，也是第二份原对话的起点。

若已知 $φ (n)$ ，则另有直接分解方法。由

φ (n) = n - (p + q) + 1

得到 $S = p + q = n - φ (n) + 1$ ，再利用 $p q = n$ ， $p, q$ 就是 $x^{2} - S x + n = 0$ 的两个根：

p, q = \frac{S \pm \sqrt{S^{2} - 4 n}}{2} .

这是因为和与积共同确定这两个因子。它说明欧拉函数与分解密切相关，同样没有证明一切解密方法都必须先知道欧拉函数。

12.5 怎样回查整条证明

若最后的加权平均已经理解，但仍对概率结论不踏实，可以分开检查三个来源：第9章解释为什么不同步就成功、为什么两边独立；第10章解释每个到达时间概率为什么不超过一半；第11章只把这些结论合起来。

若卡在基础定理，第13章补逆元、唯一分解、容斥与CRT；第14章补原根存在性；第15章补群论中的阶与计数；第16章给精确概率、统一指数与复杂度；第17章保留概念辨析和练习。补充章节按疑问查阅，不要求先把所有抽象结论学完再阅读主线。

第 13 章：补充证明：逆元、唯一分解与CRT

返回目录

这一章供遇到“这一步还没证明”时回查。第1—12章已经解释主线的定理与推导；这里补足它们背后的基础结论。可按小节标题选读，不需要一次全部读完。

13.1 从最小正线性组合证明裴蜀等式

定理。 对不全为零的整数 $a, b$ ，存在整数 $x, y$ ，使

a x + b y = gcd (a, b) .

令

S = {a x + b y : x, y \in Z, a x + b y > 0} .

集合非空：若 $a \neq 0$ ，选择 $x = 1$ 或 $- 1$ 、 $y = 0$ 即得到 $| a |$ ；否则用 $| b |$ 。由良序原理， $S$ 有最小元素 $d > 0$ ，写作 $d = a x_{0} + b y_{0}$ 。

对 $a$ 作带余除法： $a = q d + r$ ， $0 \leq r < d$ 。于是

r = a - q d = a (1 - q x_{0}) + b (- q y_{0}) .

如果 $r > 0$ ，它也是 $S$ 的元素，却比 $d$ 小，矛盾。故 $r = 0$ ，即 $d ∣ a$ 。同理 $d ∣ b$ 。

另一方面，任意正公约数 $c$ 都整除 $a, b$ 的整数线性组合，所以 $c ∣ d$ ，进而 $c \leq d$ 。因此 $d$ 既是公约数，又不小于任何正公约数，正是 $gcd (a, b)$ 。所需的 $x_{0}, y_{0}$ 已由构造给出。证毕。

关键不是猜出线性组合，而是先取最小正组合，再用带余除法排除更小的正组合。这个证明不依赖质因数分解，后面的论证因而没有循环。

13.2 互质消去律与欧几里得引理

若 $gcd (a, n) = 1$ 且 $n ∣ a b$ ，由裴蜀等式取 $a x + n y = 1$ ，乘以 $b$ ：

b = a b x + n b y .

右侧两项均被 $n$ 整除，故 $n ∣ b$ 。这就是互质消去律，其中 $n$ 不必是质数。

作为特例，若 $p$ 是质数且 $p ∣ a b$ ，则 $p ∣ a$ 或 $p ∣ b$ 。因为一旦 $p ∤ a$ ，质数的因数只有 $1, p$ ，所以 $gcd (a, p) = 1$ ，可应用消去律。这称为欧几里得引理。

质数条件不可随意删去： $6 ∣ 2 \cdot 3$ ，但 $6$ 不整除任何一个因子。反复应用欧几里得引理，可得质数若整除有限乘积，必整除至少一个因子。

13.3 模逆元存在的充要条件

$a$ 模 $n$ 的逆元是满足 $a u \equiv 1 (\mod n)$ 的整数 $u$ 。对 $n \geq 2$ ，有

a 模 n 有逆元 ⟺ gcd (a, n) = 1.

充分性：由 $a x + n y = 1$ ，取 $u = x$ 。

必要性：若 $a u - n v = 1$ ， $a, n$ 的每个公约数都整除左边，因此整除 $1$ ，所以只能为 $1$ 。

逆元在模 $n$ 意义下唯一：若 $a u \equiv a v \equiv 1$ ，则 $n ∣ a (u - v)$ ；由互质消去律， $n ∣ (u - v)$ 。

因此，当 $gcd (a, n) = 1$ 时，从 $a b \equiv a c (\mod n)$ 可以乘以逆元，推出 $b \equiv c (\mod n)$ 。这是后面约去阶乘或剩余类乘积的依据。

13.4 两个常用推论

互质因子的乘积仍与模数互质。 若 $a x + n y = 1$ 、 $b u + n v = 1$ ，相乘得到

a b x u + n (a x v + b u y + n y v) = 1.

任意 $a b, n$ 的公约数都整除 $1$ ，故 $gcd (a b, n) = 1$ 。有限多个因子可归纳处理。

互质的两个数都整除一个整数，则其乘积也整除。 若 $gcd (m, n) = 1$ 、 $m ∣ A$ 、 $n ∣ A$ ，写 $A = m t$ 。由 $n ∣ m t$ 与消去律， $n ∣ t$ ，故 $m n ∣ A$ 。

13.5 如何实际计算逆元

带余除法给出 $gcd (a, b) = gcd (b, r)$ ，因为 $a = q b + r$ 使两对数的公约数完全相同。反复除法时非零余数严格变小，最终停在最大公约数；再回代即可找到裴蜀系数。这就是扩展欧几里得算法。

例如 $40 = 13 \cdot 3 + 1$ ，所以 $1 = 40 - 13 \cdot 3$ ，从而

3^{- 1} \equiv - 13 \equiv 27 (\mod 40) .

这里逆元符号表示模运算中的整数剩余类，不是普通分数 $1 / 3$ 。

13.6 定理的准确表述

每个整数 $n > 1$ 都能写成有限个质数的乘积。除排列顺序外，质因子及其重数唯一。将相同质因子合并，可以写成

n = p_{1}^{α_{1}} \dots p_{k}^{α_{k}},

其中 $p_{i}$ 两两不同， $α_{i} \geq 1$ 。例如 $60 = 2^{2} \cdot 3 \cdot 5$ 。

“存在”和“唯一”是两个不同问题，不能只证明能拆分，就认为不可能有另一种拆分。

13.7 存在性：强归纳法

$n = 2$ 自身是质数。假设所有满足 $2 \leq m < n$ 的整数均可分解。

若 $n$ 是质数，结论立即成立。若 $n$ 是合数，可写 $n = a b$ ，其中 $1 < a, b < n$ 。由归纳假设， $a, b$ 都是质数的有限乘积，合在一起给出 $n$ 的分解。因此对所有 $n > 1$ 成立。

13.8 唯一性：配对和终止分别证明

假设

p_{1} \dots p_{r} = q_{1} \dots q_{s}

是两种分解。 $p_{1}$ 整除右侧，由欧几里得引理，它整除某个 $q_{j}$ 。两个数都是质数，所以 $p_{1} = q_{j}$ 。重排右边，将它放到第一位，再在普通整数等式中约去相同质数。

重复此步骤，每次都会找到并约去一对相同质因子。

为什么两边一定同时约完？ 假设 $r < s$ 。约去左侧全部 $r$ 个因子后，得到

1 = q_{r + 1} \dots q_{s} .

右侧至少剩一个质数，每个质数都不小于 $2$ ，故乘积大于 $1$ ，矛盾。 $r > s$ 同样矛盾。所以 $r = s$ ，每一步配对后所有质因子一一相等，重数也相同。证毕。

能够配对来自欧几里得引理；必然同时结束来自非空质数乘积大于 $1$ 。这是原对话“为什么最终同时约完”的完整回答。

13.9 最大公约数与最小公倍数的质数幂描述

给定有限多个正整数，把出现的质数统一记为 $p_{j}$ ，缺少某个质因子时指数记为 $0$ 。两个数的最大公约数取每个指数的最小值，最小公倍数取最大值：

gcd (m, n) = \prod_{j} p_{j}^{min (α_{j}, β_{j})}, lcm (m, n) = \prod_{j} p_{j}^{max (α_{j}, β_{j})} .

理由是：由唯一分解，一个正整数整除另一个，当且仅当每个质数指数都不超过对方。公约数和公倍数的条件遂逐个指数决定。

于是 $gcd (m, n) lcm (m, n) = m n$ 。一个整数同时被所有 $m_{i}$ 整除，当且仅当被 $lcm (m_{1}, \dots, m_{k})$ 整除；整数为 $0$ 的情况也显然成立。这将说明中国剩余定理的解周期。

13.10 一般容斥为何成立

令 $A_{i}$ 是能被 $p_{i}$ 整除的整数集合。统计其补集时，按所选集合个数交替加减，并把空交集解释为全部 $n$ 个整数。

对一个落入恰好 $j$ 个 $A_{i}$ 的整数，它在展开中的总权重为

\sum_{t = 0}^{j} (- 1)^{t} (\binom{j}{t}) = (1 - 1)^{j} .

若 $j = 0$ ，权重为 $1$ ；若 $j \geq 1$ ，权重为 $0$ 。所以恰好只计入互质整数，每个计入一次。这证明了容斥，而非仅把它作为未证明的工具使用。

记 $I = {1, \dots, k}$ 。不同质数互质，每个交集对应其乘积的倍数，故

φ (n) = n \sum_{J \subseteq I} (- 1)^{| J |} \prod_{i \in J} \frac{1}{p_{i}} .

空乘积取 $1$ 。展开 $\prod_{i} (1 - 1 / p_{i})$ 时，从每个括号选 $1$ 或 $- 1 / p_{i}$ 。选择负项的下标恰好形成子集 $J$ ，贡献 $(- 1)^{| J |} \prod_{i \in J} 1 / p_{i}$ ；每个子集出现一次。因此

φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p}) .

乘积公式是容斥展开的因式分解表达。 质因子指数虽影响 $n$ ，排除的倍数类别却只由不同质因子决定，所以每个质数只出现一个括号。

13.11 两两互质模数的定理

设正整数 $m_{1}, \dots, m_{k}$ 两两互质，余数 $a_{i}$ 为任意整数，令 $M = m_{1} \dots m_{k}$ 。则

x \equiv a_{i} (\mod m_{i}) (i = 1, \dots, k)

一定有解，所有解恰为 $x = x_{0} + t M$ ， $t \in Z$ 。

“唯一”指模 $M$ 的唯一剩余类，而非只有一个整数解。模数为 $1$ 的条件不限制任何整数，可以删除；若全部为 $1$ ，全部整数就是模 $1$ 的一个剩余类。以下构造处理剩余的模数。

13.12 存在性：构造对自己的模数余一、对其他余零的项

令 $M_{i} = M / m_{i}$ 。因为其他每个 $m_{j}$ 都与 $m_{i}$ 互质，第 13.4 节的乘积互质性质给出 $gcd (M_{i}, m_{i}) = 1$ 。

由裴蜀等式，取 $M_{i} u_{i} + m_{i} v_{i} = 1$ ，令 $E_{i} = M_{i} u_{i}$ 。于是

E_{i} \equiv 1 (\mod m_{i}), E_{i} \equiv 0 (\mod m_{j}) (j \neq i) .

第二式来自 $m_{j} ∣ M_{i}$ 。再取

x_{0} = \sum_{i = 1}^{k} a_{i} E_{i} = \sum_{i = 1}^{k} a_{i} M_{i} u_{i} .

对任意固定 $m_{j}$ 取模，其余项全为 $0$ ，只有 $a_{j} E_{j} \equiv a_{j}$ ，所以满足全部方程。存在性得证。

13.13 唯一性与全部解

若 $x, y$ 都是解，则每个 $m_{i}$ 都整除 $x - y$ 。由于模数两两互质，任意部分乘积仍与下一个模数互质，可反复用互质乘积整除推论，得 $M ∣ (x - y)$ 。

反过来， $x_{0} + t M$ 对各模数都与 $x_{0}$ 同余，所以仍是解。因此全部解恰为该形式。

13.14 手算构造公式

求 $x \equiv 2 (\mod 3)$ 、 $x \equiv 3 (\mod 5)$ 、 $x \equiv 2 (\mod 7)$ 。

$M = 105$ ， $M_{1} = 35$ 、 $M_{2} = 21$ 、 $M_{3} = 15$ ；各自逆元可取 $2, 1, 1$ ，因为对应乘积模自身模数均为 $1$ 。于是

x_{0} = 2 \cdot 35 \cdot 2 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 (\mod 105) .

全部解 $x = 23 + 105 t$ 。直接检验 $23$ 分别余 $2, 3, 2$ 。

13.15 相容性条件与正确周期

对任意正整数模数 $m_{1}, \dots, m_{k}$ ，方程组 $x \equiv a_{i} (\mod m_{i})$ 有解，当且仅当

gcd (m_{i}, m_{j}) ∣ (a_{i} - a_{j}) 对全部 i, j .

若有解，令 $L = lcm (m_{1}, \dots, m_{k})$ ，全部解恰为 $x = x_{0} + t L$ 。

模数不互质时，相容性有实际限制。例如 $x \equiv 2 (\mod 6)$ 与 $x \equiv 4 (\mod 9)$ 无解，因为公约数 $3$ 不整除余数差 $2$ 。互质时公约数为 $1$ ，条件自动满足，且 $L$ 等于乘积，所以标准形式是特殊情形。

13.16 两个模数：必要性

考虑 $x \equiv a (\mod m)$ 、 $x \equiv b (\mod n)$ ，记 $g = gcd (m, n)$ 。

若存在 $x$ ， $g$ 整除 $x - a$ 与 $x - b$ ，也就整除两者之差 $b - a$ 。因此 $g ∣ (b - a)$ 必要。

13.17 两个模数：充分性与构造

假设 $g ∣ (b - a)$ ，写 $m = g m^{'}$ 、 $n = g n^{'}$ 、 $b - a = g c$ ，其中 $m^{'}, n^{'}$ 互质。

先令 $x = a + m t$ ，保证第一个方程。第二个方程要求 $m t \equiv b - a (\mod n)$ ，等价于存在整数 $s$ 使

m t - n s = b - a ⟺ m^{'} t - n^{'} s = c .

用裴蜀等式取 $m^{'} u + n^{'} v = 1$ ，令 $t = c u$ 、 $s = - c v$ ，便满足要求，因此可取 $x_{0} = a + m c u$ 。充分性得证。

若 $x, y$ 均为解，则 $m, n$ 都整除 $x - y$ ，由第 13.9 节， $lcm (m, n) ∣ (x - y)$ 。反过来加上该最小公倍数的任意整数倍仍是解，因而全部解及周期成立。

13.18 非互质的手算例子

求 $x \equiv 2 (\mod 6)$ 、 $x \equiv 5 (\mod 9)$ 。公约数 $3$ 整除余数差 $3$ ，所以有解。

写 $x = 2 + 6 t$ ，代入得到 $6 t \equiv 3 (\mod 9)$ 。这一同余等价于 $2 t \equiv 1 (\mod 3)$ ：是同时将整除等式的两边及模数除以 $3$ ，并非保持原模数的无条件约分。

所以 $t \equiv 2 (\mod 3)$ ，取 $t = 2 + 3 s$ ，得

x = 14 + 18 s, x \equiv 14 (\mod 18) .

周期是 $lcm (6, 9) = 18$ ，不是乘积 $54$ 。

13.19 多个模数：为何两两相容足以给出共同解

必要性仍来自任意两个方程的差。充分性必须另证，不能只说“每一对有解，所以整体有解”。以下使用质数幂分解。

写

L = lcm (m_{1}, \dots, m_{k}) = \prod_{j = 1}^{r} p_{j}^{e_{j}} .

每个 $e_{j}$ 是所有模数中该质数指数的最大值，所以可选一个下标 $h (j)$ ，使 $p_{j}^{e_{j}} ∣ m_{h (j)}$ 。提取约束

x \equiv a_{h (j)} (\mod p_{j}^{e_{j}}) (j = 1, \dots, r) .

这些模数是不同质数的幂，两两互质，由标准形式得到公共解 $x_{0}$ 。

现在证明它满足原方程。固定 $i$ ，设 $p_{j}$ 在 $m_{i}$ 中的指数为 $f_{i j} \leq e_{j}$ 。若 $f_{i j} > 0$ ，该质数幂同时整除 $m_{i}$ 与 $m_{h (j)}$ ，故

p_{j}^{f_{i j}} ∣ gcd (m_{i}, m_{h (j)}) ∣ (a_{i} - a_{h (j)}) .

而构造保证 $x_{0} \equiv a_{h (j)} (\mod p_{j}^{e_{j}})$ ，所以降到 $p_{j}^{f_{i j}}$ 后仍成立，结合相容性得 $x_{0} \equiv a_{i}$ 模该质数幂。对 $m_{i}$ 的所有不同质数幂都成立，互质乘积整除推论给出 $m_{i} ∣ (x_{0} - a_{i})$ 。

由于 $i$ 任意，满足全部原方程。若 $L = 1$ ，则全部模数为 $1$ ，直接取任意整数即可。

若选择最大指数的模数有多个，相容性使它们的余数模该质数幂相同，因此提取约束没有歧义。

13.20 唯一性与一个多模数例子

任意两个解之差被所有 $m_{i}$ 整除，因此被 $L$ 整除； $x_{0} + t L$ 又总是解。所以解模 $L$ 唯一。 $L$ 也是解集合的最小正平移周期：任何保持解的正平移量都必须被全部模数整除，因此被 $L$ 整除。

例如取 $m_{1} = 12, m_{2} = 18, m_{3} = 20$ ，余数分别为 $5, 11, 17$ 。三个公约数为 $6, 4, 2$ ，都整除对应余数差。 $L = 180 = 4 \cdot 9 \cdot 5$ ，可提取

x \equiv 1 (\mod 4), x \equiv 2 (\mod 9), x \equiv 2 (\mod 5) .

取 $x_{0} = 137$ ，逐项检验模 $12, 18, 20$ 分别余 $5, 11, 17$ ，故全部解为 $137 + 180 t$ 。

第 14 章：补充证明：质数为什么一定有原根

返回目录

第5章已经说明原根的定义和存在性证明的路线。这一章只解决存在性与相关阶公式，适合想追问“每个质数为什么都能找到这样的底数”时阅读。证明先准备两个工具，再限制多项式的根数，最后逐个拼出所需的质数幂周期。

14.1 辅助引理一：一个幂的阶

若 $a$ 的阶为 $d$ ， $m \geq 0$ ，则

{ord}_{n} (a^{m}) = \frac{d}{gcd (d, m)} .

先设 $m \geq 1$ 。令 $h = gcd (d, m)$ ，写 $d = h d^{'}$ 、 $m = h m^{'}$ ，其中 $gcd (d^{'}, m^{'}) = 1$ 。对正整数 $k$ ，

(a^{m})^{k} \equiv 1 ⟺ d ∣ m k ⟺ d^{'} ∣ m^{'} k ⟺ d^{'} ∣ k .

最后一步用互质消去律。所以最小正 $k$ 是 $d^{'}$ 。当 $m = 0$ 时， $a^{0}$ 的阶为 $1$ ，右边也是 $d / gcd (d, 0) = 1$ 。这补全了原对话原根证明中直接使用的公式，也覆盖后面循环群计数的单位元。

14.2 辅助引理二：阶互质时乘积的阶

设 ${ord}_{n} (a) = r$ 、 ${ord}_{n} (b) = s$ ，且 $gcd (r, s) = 1$ 。模整数的乘法可交换，因此

{ord}_{n} (a b) = r s .

先有 $(a b)^{r s} = (a^{r})^{s} (b^{s})^{r} \equiv 1$ ，故 $t = {ord}_{n} (a b)$ 整除 $r s$ 。

又 $(a b)^{t} \equiv 1$ 。取 $r$ 次幂，得到 $a^{r t} b^{r t} \equiv 1$ 。 $a^{r t} \equiv 1$ ，所以 $b^{r t} \equiv 1$ ，进而 $s ∣ r t$ 。由 $r, s$ 互质，推出 $s ∣ t$ 。同理 $r ∣ t$ ，再由互质乘积整除推论， $r s ∣ t$ 。结合 $t ∣ r s$ ，得 $t = r s$ 。

这样无需使用负指数也能完成证明。在一般群中还必须要求两个元素可交换，否则幂不一定可拆开。

若阶不互质，结论未必成立：模 $7$ 时 $2, 4$ 的阶均为 $3$ ，但 $2 \cdot 4 \equiv 1$ ，乘积的阶为 $1$ 。

对任意互质于模数的 $a, b$ ，令 $L = lcm (r, s)$ ，则 $(a b)^{L} \equiv 1$ ，故乘积的阶总整除 $L$ 。互质阶条件保证这个整除进一步达到等号。

14.3 为什么非零多项式的根数不超过次数

在模质数 $p$ 的系数运算中，设 $f$ 的次数为 $m$ ，最高次系数模 $p$ 不为 $0$ 。它最多有 $m$ 个不同剩余类的根。

先证明因式分解的依据。对每个 $j \geq 1$ ，

x^{j} - r^{j} = (x - r) (x^{j - 1} + x^{j - 2} r + \dots + r^{j - 1}) .

逐项相加给出 $f (x) - f (r) = (x - r) h (x)$ 。若 $f (r) \equiv 0$ ，便在模 $p$ 的多项式环里得到 $f (x) = (x - r) h (x)$ ， $h$ 次数为 $m - 1$ 。

$m = 0$ 时非零常数没有根。归纳地，若没有根结论显然；若有根 $r$ ，对另一个不同根 $s$ ，有 $(s - r) h (s) \equiv 0$ 。因为 $p$ 质数且 $s - r ≢ 0$ ，可消去 $s - r$ ，故 $h (s) \equiv 0$ 。归纳假设使其他根最多 $m - 1$ 个，加上 $r$ 至多 $m$ 个。证毕。

质数条件在此保证非零元素可逆。模 $8$ 的多项式 $x^{2} - 1$ 有 $1, 3, 5, 7$ 四个根，已超过次数，说明合数模数不能照搬。

14.4 每个质数都有原根：完整构造证明

$p = 2$ 时，非零剩余类只有 $1$ ，其阶为 $1 = p - 1$ ，已经是原根。以下设 $p > 2$ ，令

N = p - 1 = \prod_{i = 1}^{k} q_{i}^{e_{i}},

其中 $q_{i}$ 为不同质数。先为每个最大质数幂构造一个对应阶的元素。

第一步：找到不被较短指数消掉的元素。 多项式 $x^{N / q_{i}} - 1$ 次数为 $N / q_{i} < N$ ，故最多有 $N / q_{i}$ 个根，而非零剩余类有 $N$ 个。因此可选择非零 $a_{i}$ ，使

a_{i}^{N / q_{i}} ≢ 1 (\mod p) .

第二步：识别阶中的完整质数幂。 令 $t_{i} = {ord}_{p} (a_{i})$ 。由第 4 章， $t_{i} ∣ N$ ，但 $t_{i} ∤ N / q_{i}$ ；否则幂必等于 $1$ 。

$N / q_{i}$ 与 $N$ 只在 $q_{i}$ 的指数上差 $1$ 。 $t_{i}$ 的其他质数指数已由 $t_{i} ∣ N$ 限制，若 $q_{i}$ 的指数也至多 $e_{i} - 1$ ，便会整除 $N / q_{i}$ ，矛盾。因此

t_{i} = q_{i}^{e_{i}} s_{i}, gcd (q_{i}, s_{i}) = 1.

第三步：除去阶中的其他因子。 取 $b_{i} = a_{i}^{s_{i}}$ 。因为 $s_{i} ∣ t_{i}$ ，由幂的阶公式，

{ord}_{p} (b_{i}) = \frac{t_{i}}{gcd (t_{i}, s_{i})} = \frac{t_{i}}{s_{i}} = q_{i}^{e_{i}} .

第四步：合并各个互质阶。 取 $g = b_{1} \dots b_{k}$ 。各阶为不同质数的幂，两两互质；模乘法可交换。反复使用第 14.2 节，每次累积阶仍与下一个阶互质，得到

{ord}_{p} (g) = \prod_{i} q_{i}^{e_{i}} = N = p - 1.

所以 $g$ 是原根。证毕。

“每个元素的阶都整除 $p - 1$ ”本身不足以证明有人达到 $p - 1$ 。多项式根数上界负责提供元素，幂的阶公式负责提取质数幂，互质阶乘积引理负责拼成完整阶。

14.5 原根有多少个

取一个模 $p$ 的原根 $g$ ， $N = p - 1$ 。全部非零剩余类可唯一表示为 $g^{m}$ ， $1 \leq m \leq N$ 。由幂的阶公式，

{ord}_{p} (g^{m}) = \frac{N}{gcd (N, m)} .

因此 $g^{m}$ 是原根，当且仅当 $gcd (N, m) = 1$ ，共有 $φ (N)$ 个。所以模 $p$ 的原根数为 $φ (p - 1)$ 。 $p = 2$ 时用 $φ (1) = 1$ ，结论仍成立。

模数	原根个数	全部原根代表
5	2	2、3
7	2	3、5
11	4	2、6、7、8
13	4	2、6、7、11
17	8	3、5、6、7、10、11、12、14

14.6 原根判定与合数反例

设 $p ∤ g$ ， $N = p - 1$ 的不同质因子为 $q_{i}$ 。则

g 是原根 ⟺ g^{N / q_{i}} ≢ 1 (\mod p) 对全部 q_{i} .

必要性：阶为 $N$ 时不整除任何 $N / q_{i}$ 。

充分性：令阶为 $d ∣ N$ 。若 $d < N$ ，商 $N / d > 1$ 有某个质因子 $q_{i}$ ，于是 $d ∣ N / q_{i}$ ，推出相应幂等于 $1$ ，矛盾。 $p = 2$ 时没有需检验的质因子，非零条件已唯一确定原根。

例：模 $17$ 时 $N = 16 = 2^{4}$ 。 $3^{4} \equiv 13$ ， $3^{8} \equiv 13^{2} \equiv 16 ≢ 1$ ，所以 $3$ 为原根。

模 $8$ 的互质代表 $1, 3, 5, 7$ 全部平方为 $1$ ，因此阶最多为 $2$ ，而 $φ (8) = 4$ ；故没有原根。

一般分类是：在 $n \geq 2$ 的约定下，有原根的模数恰好为 $2, 4, q^{k}, 2 q^{k}$ ，其中 $q$ 为奇质数， $k \geq 1$ 。此分类是拓展结论，本篇没有给出其完整证明；可参看 Yale 数论与密码学课程讲义。

第 15 章：补充证明：群、阶与欧拉函数计数

返回目录

第10章已经从幂阶公式解释循环群的阶计数。这里保留一般群中的定义与完整证明，并补上“元素阶整除群阶”的陪集论证。群是概括模乘法的语言；下面先从可逆剩余类说明运算，再引入一般定义。概率符号的严格定义也放在本章末尾，供回查。

15.1 从模乘法进入群的语言

前面已经证明的模逆元、幂的周期与原根，可以用群的语言统一表达。群是带一种运算的集合，运算满足：封闭、结合律、有单位元、每个元素有逆元。若运算还满足交换律，称为交换群。群的阶是元素个数，记为 $| G |$ ；它与某个元素的阶是两种不同的数量。

对 $n \geq 2$ ，模 $n$ 的互质剩余类组成

U_{n} = (Z / n Z)^{\times} = {[a]_{n} : gcd (a, n) = 1} .

其运算为剩余类乘法。第 13.4 节保证乘积仍互质，所以运算封闭；整数乘法给出结合律与交换律； $[1]_{n}$ 是单位元；第 13.3 节保证每个元素有逆元，而且逆元也与 $n$ 互质。因此 $U_{n}$ 是有限交换群， $| U_{n} | = φ (n)$ 。

对质数 $p$ ， $U_{p}$ 就是全部非零剩余类，阶为 $p - 1$ 。第 14 章已经完整证明原根存在，所以某个 $g$ 的幂遍历 $U_{p}$ 。这就是说

U_{p} = ⟨ g ⟩

是循环群。这里“循环”表示一个元素的幂生成整个群；它是比“每个元素的幂都有周期”更强的性质。

一般模数不保证循环： $U_{8} = {1, 3, 5, 7}$ 有四个元素，却没有阶为四的元素，因而任何单个元素都无法生成全群。

15.2 有限群中的元素阶与循环子群

以下暂用 $1_{G}$ 表示群单位元。对有限群中的元素 $a$ ，它的阶是满足 $a^{d} = 1_{G}$ 的最小正整数 $d$ 。

先说明这个正整数一定存在。若 $| G | = N$ ， $1_{G}, a, a^{2}, \dots, a^{N}$ 共 $N + 1$ 项，必有两项相同。设 $a^{i} = a^{j}$ 、 $i < j$ ，乘以 $a^{- i}$ 得 $a^{j - i} = 1_{G}$ 。由良序原理可以取最小正指数。

与第 4.2 节同样作带余除法，可以证明对 $k \geq 0$ ，

a^{k} = 1_{G} ⟺ d ∣ k .

因此 $1_{G}, a, \dots, a^{d - 1}$ 两两不同，且任何非负整数幂都等于其中某一项。这个集合记为 $H = ⟨ a ⟩$ 。它包含单位元；两项乘积仍是一个幂； $a^{j}$ 的逆元为 $a^{d - j}$ ，经指数取余仍在集合中。因此 $H$ 是 $G$ 的子群，恰有 $d$ 个元素。

在一般群中也可以使用整数次幂，负次幂由逆元定义；这里的计数只用非负代表。

15.3 陪集划分与拉格朗日定理的完整证明

设 $H$ 是有限群 $G$ 的子群。对 $g \in G$ ，左陪集定义为

g H = {g h : h \in H} .

第一，每个陪集与 $H$ 等大。 映射 $h \mapsto g h$ 是双射，逆映射为 $x \mapsto g^{- 1} x$ ，故 $| g H | = | H |$ 。

第二，两个陪集相交就相同。 若 $z = g_{1} h_{1} = g_{2} h_{2}$ ，其中 $h_{1}, h_{2} \in H$ ，则

g_{2}^{- 1} g_{1} = h_{2} h_{1}^{- 1} \in H .

记此元素为 $h_{0}$ ，有 $g_{1} = g_{2} h_{0}$ 。对子群内的 $h$ ， $h_{0} h \in H$ ，所以 $g_{1} H \subseteq g_{2} H$ ；反用 $h_{0}^{- 1} \in H$ 得反向包含。故两个陪集完全相同。

第三，陪集覆盖全群。 每个 $g \in G$ 都属于 $g H$ ，因为 $g = g 1_{G}$ 。

综上，不同左陪集将 $G$ 划分成若干互不重叠、每份恰有 $| H |$ 个元素的集合。若有 $k$ 个不同陪集，则

| G | = k | H |, | H | ∣ | G | .

这就是拉格朗日定理。取 $H = ⟨ a ⟩$ ，便得

ord (a) ∣ | G | .

证明没有使用交换律，适用于任意有限群。

整除条件不保证每个因数都实现为元素阶。 例如 $U_{8}$ 的阶为 $4$ ，其元素阶分别为 $1, 2, 2, 2$ ，没有阶为 $4$ 的元素。后面按每个因数精确计数，依赖的是循环群这一额外条件。

15.4 循环群中的幂阶公式，包括零指数

设 $G = ⟨ g ⟩$ ， $| G | = N$ ，即 $g$ 的阶为 $N$ 。每个元素唯一写为 $g^{k}$ ，其中 $0 \leq k < N$ 。第 14.1 节的论证在群中原样成立：对 $k \geq 0$ ，

ord (g^{k}) = \frac{N}{gcd (N, k)} .

若 $k > 0$ ，写 $N = c n^{'}$ 、 $k = c k^{'}$ ， $c = gcd (N, k)$ 。对正整数 $m$ ，

(g^{k})^{m} = 1_{G} ⟺ N ∣ k m ⟺ n^{'} ∣ k^{'} m ⟺ n^{'} ∣ m .

最后一步用 $gcd (n^{'}, k^{'}) = 1$ 与互质消去律。因此最小正 $m$ 为 $n^{'} = N / c$ 。

若 $k = 0$ ， $g^{0} = 1_{G}$ 的阶为 $1$ ，而 $gcd (N, 0) = N$ ，公式同样给出 $1$ 。这一步补足了概率计数必须包含单位元的边界。

15.5 为什么阶为 d 的元素恰好有欧拉函数那么多个

设 $d ∣ N$ ，令 $s = N / d$ 。由刚才的公式，

ord (g^{k}) = d ⟺ gcd (N, k) = s .

右边要求 $s ∣ k$ ，写 $k = s t$ 。由于 $0 \leq k < N = s d$ ，恰有 $0 \leq t < d$ 。并且

gcd (N, k) = gcd (s d, s t) = s gcd (d, t) .

这个等式也可由第 13.9 节的质数指数逐项取最小值证明。因此

ord (g^{k}) = d ⟺ {\begin{cases} k = (N / d) t, \\ 0 \leq t < d, \\ gcd (t, d) = 1. \end{cases}

当 $d > 1$ ，这样的 $t$ 恰有 $φ (d)$ 个，因为 $0$ 不互质，统计范围与 $1, \dots, d$ 等价；当 $d = 1$ ，只有 $t = 0$ ，且 $gcd (0, 1) = 1$ ，也与 $φ (1) = 1$ 一致。每个 $t$ 对应不同的 $g^{k}$ ，所以

# {x \in G : ord (x) = d} = φ (d) .

若 $d ∤ N$ ，由拉格朗日定理个数为 $0$ 。由计数结果可见，在循环群中每个正因数确实都被实现。

取 $N = 2^{α}$ ，各元素阶只能为 $2^{t}$ ， $0 \leq t \leq α$ 。其数量为

{\begin{cases} 1, & t = 0, \\ 2^{t - 1}, & 1 \leq t \leq α . \end{cases}

因为 $t \geq 1$ 时模 $2^{t}$ 的互质代表恰为奇数，有一半。总数检查为 $1 + \sum_{t = 1}^{α} 2^{t - 1} = 2^{α}$ ；没有遗漏其他阶。这就是第 10 章到达时间分布中的计数依据。

15.6 原根存在性的另一条证明：所有阶的最小公倍数

新增对话给出另一种证明，可以与第 14.4 节的逐个质数幂构造对照。设 $p > 2$ ，令

E = lcm {{ord}_{p} (a) : a \in U_{p}} .

每个阶均整除 $p - 1$ ，故 $E ∣ (p - 1)$ 。另一方面，每个非零剩余类都满足 $a^{E} = 1$ 。多项式 $x^{E} - 1$ 因而至少有 $p - 1$ 个根；由第 14.3 节的根数上界， $p - 1 \leq E$ 。于是 $E = p - 1$ 。

还需要说明有元素的阶恰好达到 $E$ 。写 $E = \prod_{i} ℓ_{i}^{c_{i}}$ 。由于是有限多个阶的最小公倍数，对于每个最大质数幂 $ℓ_{i}^{c_{i}}$ ，存在某个 $a_{i}$ ，其阶为 $ℓ_{i}^{c_{i}} t_{i}$ ，且 $gcd (ℓ_{i}, t_{i}) = 1$ 。取 $b_{i} = a_{i}^{t_{i}}$ ，幂阶公式给出阶为 $ℓ_{i}^{c_{i}}$ 。这些阶两两互质，模乘法可交换，第 14.2 节给出 $g = \prod_{i} b_{i}$ 的阶为 $E = p - 1$ 。故 $g$ 是原根。 $p = 2$ 单独取 $g = 1$ 即可。

这段“最小公倍数可以由一个元素的阶达到”的构造对有限交换群成立，不能去掉交换条件。例如三元素置换群 $S_{3}$ 的元素由恒等、换位和三循环组成，阶分别为 $1, 2, 3$ ，最小公倍数为 $6$ ，却没有阶为 $6$ 的元素。

15.7 样本空间、事件与随机变量

本篇只需要有限概率，不需要先学习连续分布或测度论。设有限样本空间 $Ω$ 的每个结果 $ω$ 有概率 $p_{ω} \geq 0$ ，并满足 $\sum_{ω \in Ω} p_{ω} = 1$ 。事件是其中一个子集 $A$ ，其概率为 $P (A) = \sum_{ω \in A} p_{ω}$ 。互不相交事件的概率可以相加。

若所有结果等概率，称为均匀分布，此时

P (A) = \frac{| A |}{| Ω |} .

随机变量 $X$ 是由结果决定的数或标签。事件 $X = t$ 指所有满足这个条件的结果，因此

P (X = t) = \sum_{ω : X (ω) = t} p_{ω}, \sum_{t} P (X = t) = 1.

最后一个等式来自不同取值的事件将样本空间划分。并非任意一组概率的和都为 $1$ ；这里使用的是某个随机变量全部互斥取值的概率。

15.8 双射保持均匀，等大小原像也保持均匀

若 $X$ 在有限集合 $S$ 上均匀， $f : S \to R$ 是一个映射，则对 $y \in R$ ，

P (f (X) = y) = \frac{# {x \in S : f (x) = y}}{| S |} .

这直接由均匀计数得到。如果 $f$ 是双射，每个原像恰有一个元素，输出在 $R$ 上均匀。如果 $f$ 是满射，而且每个原像恰有相同的 $c$ 个元素，则 $| S | = c | R |$ ，输出仍在 $R$ 上均匀，概率为 $c / | S | = 1 / | R |$ 。

输出均匀需要检验原像大小，不能仅因为输入均匀就断定。 例如均匀取 $X \in {0, 1, 2}$ ，映射 $X mod 2$ 取 $0$ 的概率为 $2 / 3$ ，取 $1$ 的概率为 $1 / 3$ 。

对 $k$ 均匀取自 $0, \dots, M u - 1$ ，映射 $k \mapsto k mod M$ 的每个原像为

j, j + M, \dots, j + (u - 1) M,

恰有 $u$ 项，故余数均匀。若 $gcd (w, M) = 1$ ， $j \mapsto w j mod M$ 又是双射：相同像经互质消去律推出相同原像，有限同大小集合上的单射就是双射。两步合起来仍保持均匀。

15.9 条件概率、独立性与全概率公式

当 $P (A) > 0$ 时，条件概率定义为

P (B ∣ A) = \frac{P (A \cap B)}{P (A)} .

随机变量 $X, Y$ 独立，表示对其全部取值 $x, y$ ，

P (X = x, Y = y) = P (X = x) P (Y = y) .

因此，在 $P (X = x) > 0$ 时， $P (Y = y ∣ X = x) = P (Y = y)$ 。零概率条件事件不使用这个除法。

设 $A_{t}$ 将样本空间划分成互不相交的事件，则 $B$ 被 $B \cap A_{t}$ 划分，所以

P (B) = \sum_{t} P (B \cap A_{t}) = \sum_{t : P (A_{t}) > 0} P (A_{t}) P (B ∣ A_{t}) .

这就是有限全概率公式。等号的依据分别是事件划分和条件概率定义，并不需要先假设独立。

如果 $X, Y$ 独立，分别只依赖它们的 $f (X), g (Y)$ 也独立。固定输出 $u, v$ ，将原像事件展开：

\begin{aligned} P (f (X) = u, g (Y) = v) & = \sum_{x : f (x) = u} \sum_{y : g (y) = v} P (X = x) P (Y = y) \\ = P (f (X) = u) P (g (Y) = v) . \end{aligned}

这里强调“分别”：若两个新变量都依赖同一个输入，不能自动断言独立。

第 16 章：补充：精确概率、统一指数与运行时间

返回目录

第11章的至少一半已经证明完了。这一章回答三个额外问题：实际概率是多少，指数条件能否再放宽，每轮计算需要多长时间。第一次理解加权上界时可以跳过这一章。

16.1 精确概率公式与最差情形

这里延续第10章的记号： $p - 1 = 2^{α} u$ ，再写 $q - 1 = 2^{β} v$ ，其中 $u, v$ 为奇数， $α, β \geq 1$ 。下面算的是均匀选互质底数时的精确概率。

令 $m_{0} = min (α, β)$ 。两边有正概率的共同取值为 $0, 1, \dots, m_{0}$ 。代入分布，

\begin{aligned} P (失败) & = \frac{1 + \sum_{t = 1}^{m_{0}} 2^{2 t - 2}}{2^{α + β}} \\ = \frac{1 + \sum_{j = 0}^{m_{0} - 1} 4^{j}}{2^{α + β}} \\ = \frac{1 + (4^{m_{0}} - 1) / 3}{2^{α + β}} \\ = \frac{4^{m_{0}} + 2}{3 \cdot 2^{α + β}} . \end{aligned}

因此

P (成功) = 1 - \frac{4^{m_{0}} + 2}{3 \cdot 2^{α + β}} .

这些是互质均匀抽样下的精确概率，不依赖 $K$ 中多出的奇因子或因子 $2$ ：前者在指数子群中作排列，后者只延长序列已经为 $1$ 的尾部。

$α$	$β$	失败概率	成功概率
1	1	$1 / 2$	$1 / 2$
2	1	$1 / 4$	$3 / 4$
2	2	$3 / 8$	$5 / 8$
3	3	$11 / 32$	$21 / 32$
2	4	$3 / 32$	$29 / 32$

若 $α = β = m_{0}$ ，失败概率为 $1 / 3 + 2 / (3 \cdot 4^{m_{0}})$ ； $m_{0} = 1$ 时为 $1 / 2$ ，以后严格减小。若两者不同，分母进一步乘以 $2^{| α - β |}$ ，失败概率更小。因此最低成功概率 $1 / 2$ 确实在 $α = β = 1$ 达到。取 $p = 3, q = 7$ 即为一个实例。

16.2 卡迈克尔函数：统一周期与单个元素周期

对 $n \geq 2$ ，令 $U_{n}$ 为互质剩余类。定义 $λ (n)$ 为所有 $a \in U_{n}$ 都满足 $a^{L} \equiv 1$ 的最小正整数 $L$ 。

由第 4.2 节，一个 $L$ 对全部元素可用，当且仅当它被每个元素的阶整除。因此

λ (n) = lcm {{ord}_{n} (a) : a \in U_{n}}, {ord}_{n} (a) ∣ λ (n) ∣ φ (n) .

最右边整除来自每个阶均整除 $φ (n)$ ，所以其最小公倍数也整除。模 $8$ 时阶分别为 $1, 2, 2, 2$ ，故 $λ (8) = 2 < 4 = φ (8)$ 。

对质数 $p$ ，原根的存在保证 $λ (p) = p - 1$ 。对两个不同质数 $p, q$ ，中国剩余定理把 $U_{p q}$ 对应到 $U_{p} \times U_{q}$ ，并且一个幂等于 $1$ 当且仅当两个坐标都等于 $1$ ，所以

λ (p q) = lcm (p - 1, q - 1) .

充分性：该最小公倍数使两个坐标的幂都为 $1$ 。必要性：由标准中国剩余定理可选互质元素，其模 $p$ 坐标为原根、模 $q$ 坐标为 $1$ ，所以任意统一指数必须被 $p - 1$ 整除；交换坐标又得 $q - 1$ 整除它，因而被两者最小公倍数整除。

三种指数的区别是：阶针对一个底数， $λ (n)$ 针对全部互质底数的最小统一指数， $φ (n)$ 是互质底数个数，同时提供一个统一指数。一般 $λ$ 的质数幂公式及全部结构不在本篇展开。

16.3 我们真正需要的是一个正的统一指数倍数

有效指数满足

e d \equiv 1 (\mod λ (n)), λ (n) = lcm (p - 1, q - 1) .

这个条件与 RFC 8017 第 3.2 节一致。令 $K = e d - 1$ ，则 $λ (n) ∣ K$ 。原对话使用更强的 $φ (n) ∣ K$ ；本章的全部证明只需要较弱条件。

要求 $K > 0$ 。 正整数 $e > 1, d \geq 1$ 可以保证这一点； $e = d = 1$ 给出 $K = 0$ ，无法把它写成后面所需的有限二次幂分解。它虽满足形式同余，却是公开的恒等幂运算，不能纳入这里的分解归约条件。

将 $K$ 中所有因子 $2$ 提取出来，得到唯一分解

K = 2^{s} r, r > 0 为奇数 .

因为 $p, q$ 为奇质数， $p - 1, q - 1$ 都为偶数，故 $s \geq 1$ 。对任何 $a \in U_{n}$ ，费马小定理分别给出 $a^{K} \equiv 1$ 模 $p$ 与模 $q$ ，再由 CRT 合并得

a^{K} \equiv 1 (\mod n) .

算法知道的是 $K$ ，无需知道 $λ (n)$ 或 $φ (n)$ 的实际数值。

16.4 有限次失败与期望多项式时间

第 11 章已经证明互质底数的一次成功概率至少为 $1 / 2$ 。在全部 $1, \dots, n - 1$ 中抽样时，非互质分支直接成功；条件于互质时仍然均匀。因此全部候选的一次成功概率也至少为 $1 / 2$ 。

独立重复 $k$ 次仍失败的概率至多为 $2^{- k}$ 。例如 $k = 20$ ，上界为 $1 / 1048576 \approx 9.54 \times 10^{- 7}$ 。这不保证每个随机序列都成功。

无限重试的算法一旦输出就必正确，期望尝试次数至多为 $2$ ，称为 Las Vegas 型随机算法；限次版本可以在未找到因子时明确报告失败。不能把“报告失败”写成输出一个未经验证的因子。

复杂度按输入位数计算。反复除以 $2$ 最多进行 $O (\log K)$ 次，快速幂需要 $O (\log r)$ 次模乘，连续平方最多 $s \leq ⌊ \log_{2} K ⌋$ 次；gcd 和整数运算均可在输入位数的多项式时间完成。期望总时间因此是 $\log n + \log e + \log d$ 的多项式，而不是与巨大整数 $K$ 的数值成正比。通常 RSA 指数代表小于 $n$ ，此时也可按 $\log n$ 控制。

第 17 章：辨清几个计数问题，再用练习回查

返回目录

本章保留原对话问过的素数数量、质因子数量及欧拉函数的区别。解析数论的渐近公式只作拓展，不参加前面的RSA证明。练习先挑你刚读过的主题，解答用于核对步骤。

17.1 三种“个数”不要混淆

问题	记号	例子
不超过 $x$ 的素数有多少个	$π (x)$	$π (12) = 5$ ：2、3、5、7、11
$n$ 有多少种不同质因子	$ω (n)$	$ω (360) = 3$
$n$ 的质因子算重数后有多少个	$Ω (n)$	$Ω (360) = 3 + 2 + 1 = 6$
代表范围内与 $n$ 互质的整数有多少个	$φ (n)$	$φ (360) = 96$

如果 $n = p_{1}^{α_{1}} \dots p_{k}^{α_{k}}$ ，则 $ω (n) = k$ 、 $Ω (n) = \sum_{i} α_{i}$ ，并约定 $ω (1) = Ω (1) = 0$ 。因每个质因子至少为 $2$ ， $n \geq 2^{Ω (n)}$ ，所以

ω (n) \leq Ω (n) \leq ⌊ \log_{2} n ⌋ .

若有 $k$ 个不同质因子，把它们排序后第 $i$ 个不小于第 $i$ 个质数，所以 $n$ 至少是前 $k$ 个质数的乘积。因此 $n < 6$ 时最多一种， $n < 30$ 时最多两种， $n < 210$ 时最多三种。这个上界讨论的是最大可能数量，不能当成给定整数的实际数量。

17.2 素数计数与渐近公式：只介绍拓展结论

素数定理为

π (x) \sim \frac{x}{\ln x} (x \to \infty) .

$\sim$ 表示两者比值趋于 $1$ ，不是精确相等；相对误差趋于 $0$ ，也不意味着绝对误差趋于 $0$ 。对整数 $n$ ，“小于 $n$ ”的计数是 $π (n - 1)$ ，不是 $π (n)$ 。参看 Carl Pomerance 的数论讲义。

上限 $n$	不超过 $n$ 的素数实际个数	$n / \ln n$ （约）
10	4	4.3
100	25	21.7
1000	168	144.8
10000	1229	1085.7
100000	9592	8685.9
1000000	78498	72382.4

接近大数 $x$ 的整数“成为素数的密度约为 $1 / \ln x$ ”是一种启发式解释，不是证明。对数积分是更精细的经典近似；采用从 $2$ 起积分的记号时，可写 ${Li}_{2} (x) = \int_{2}^{x} d t / \ln t$ 。它与采用主值积分定义的 $li (x)$ 相差常数，记号应说明约定。

原对话还提到不同质因子数的最大值与平均值，其渐近量级分别是 $\ln x / \ln \ln x$ 与 $\ln \ln x$ 。它们是关于一批整数的统计结论，不是计算 $ω (n)$ 的精确公式。为把平均与正常数量分开，准确写成

max_{1 \leq m \leq x} ω (m) \sim \frac{\ln x}{\ln \ln x}, \frac{1}{⌊ x ⌋} \sum_{m \leq x} ω (m) \sim \ln \ln x .

Hardy–Ramanujan 定理的核心是“正常数量”：对每个固定 $ε > 0$ ，除占比趋于 $0$ 的例外整数外， $ω (m)$ 接近 $\ln \ln m$ ，相对偏差小于 $ε$ 。平均值结论与正常数量结论相关，但不是同一个陈述；这一区别可参看 Carl Pomerance 关于数量阶的讲义。

以上解析数论结论不在本篇的证明范围内，也不参与 RSA 正确性证明。拓展资料可参看数论笔记中的算术函数阶。

17.3 练习与解答

题 1。 求 $3^{100}$ 模 $7$ 的余数。
解： $100 \equiv 4 (\mod 6)$ ， $3^{100} \equiv 3^{4} = 81 \equiv 4$ 。

题 2。 对任意整数 $a$ ， $a^{6} \equiv 1 (\mod 7)$ 与 $a^{7} \equiv a (\mod 7)$ 哪个必成立？
解：第二个。第一个还需 $7 ∤ a$ ，取 $a = 7$ 即得反例。

题 3。 解 $2 x \equiv 3 (\mod 5)$ 。
解： $2$ 的逆元为 $3$ ，所以 $x \equiv 9 \equiv 4 (\mod 5)$ 。

题 4。 已知 ${ord}_{17} (3) = 16$ ，求 $3^{4}$ 的阶。
解： $16 / gcd (16, 4) = 4$ 。直接检验 $3^{4} \equiv 13$ ， $13^{2} \equiv - 1$ ， $13^{4} \equiv 1$ 。

题 5。 解 $x \equiv 1 (\mod 4)$ 、 $x \equiv 3 (\mod 6)$ 。
解：公约数 $2$ 整除余数差 $2$ ，有解。写 $x = 1 + 4 t$ ，得到 $2 t \equiv 1 (\mod 3)$ ，所以 $t \equiv 2$ ， $x \equiv 9 (\mod 12)$ 。

题 6。 对 $n = 55, e = 3, d = 27$ ，消息 $m = 0, 11, 54$ 是否都能恢复？
解：是。第 7.3 节已覆盖任意消息，包括 $0$ 与质因子倍数。加密余数分别为 $0, 11, 54$ ，相应解密余数也是它们本身。

题 7。 一个 $12$ 阶循环群中，阶为 $1, 2, 3, 4, 6, 12$ 的元素分别有多少个？解：分别为 $φ (d) = 1, 1, 2, 2, 2, 4$ ，总和为 $12$ ；其他正整数不整除 $12$ 时个数为 $0$ 。

题 8。 已知 $h$ 模 $13$ 的阶为 $4$ ， $h = 8$ ，求 $h^{2026}$ 。解：指数对 $4$ 取余为 $2$ ，幂的值仍模 $13$ ，所以 $8^{2026} \equiv 8^{2} \equiv 12 (\mod 13)$ 。

题 9。 两个独立随机变量的分布为 $(1 / 4, 1 / 4, 1 / 2)$ 与 $(1 / 2, 1 / 2, 0)$ ，它们相等的概率是多少？为何仍可写上界 $1 / 2$ ？解：按相同位置作乘积并求和得 $1 / 4$ 。第二分布每项至多 $1 / 2$ ，以第一分布为权重，权重总和为 $1$ ，所以通用上界为 $1 / 2$ 。上界不等于精确值。

题 10。 对 $n = 55, e = 3, d = 7$ ，连续平方分解仍可用吗？解： $e d - 1 = 20 = λ (55)$ ，不是 $φ (55) = 40$ 的倍数，但条件已足够。 $20 = 2^{2} \cdot 5$ ；取 $a = 2$ 得 $32, 34, 1$ ，照样提取 $11, 5$ 。互质底数成功概率仍为 $3 / 4$ 。

题 11。 若 $p - 1$ 与 $q - 1$ 中因子 $2$ 的次数分别为 $2, 4$ ，互质均匀底数一次尝试的成功概率是多少？解： $m_{0} = 2$ ，失败概率为 $(4^{2} + 2) / (3 \cdot 2^{6}) = 3 / 32$ ，成功概率为 $29 / 32$ 。

题 12。 单次失败概率为 $1 / 4$ ，独立重复 $3$ 次仍全部失败的概率与期望尝试次数是多少？解：分别为 $(1 / 4)^{3} = 1 / 64$ 与 $1 / (1 - 1 / 4) = 4 / 3$ 。若不独立重选，这些式子未必成立。

第 18 章：从原问题回到笔记，以及怎样分享

返回目录

18.1 第一份对话的21轮

这里按原来的追问顺序提供回查入口。原对话中选择的文字与公式显示问题也保留为来源数据；对于未直接查看的截图，不声称已经读过图像。

轮次	原来的问题或关注点	在哪里接着读
1	费马小定理及简单应用	第2章
2	为什么缩减指数需要互质	第1章、第2章
3	每个数为什么只有一种质因数分解	第13章
4	用过的基础结论还没有证明	第13章
5	两边为什么一定同时约完	第13章唯一性证明
6	小于某个数的素数数量	第17章
7	质因子的种数及数量上界	第17章
8	想找欧拉相关的计数公式	第3章
9	展开欧拉函数公式	第3章、第13章
10	为什么乘积展开就是容斥	第3章、第13章
11	欧拉函数与小定理结合的结论	第3章
12	继续讲乘法阶	第4章
13	继续讲原根及存在性	第5章、第14章
14	原根回答里的公式显示异常	第5章、第14章重新排版
15	上传截图指出显示问题	只保留附件引用；原根证明在第14章重新排版
16	阶互质时乘积阶为什么相乘	第14章
17	欧拉定理怎样联系密码学	第7章
18	所需的两个指数一定存在吗	第7章、第13章
19	消息不互质时怎样证明RSA	第7章
20	中国剩余定理的一般形式	第6章、第13章
21	两种形式的详细证明	第13章

18.2 第二份对话的11轮与一条补充

后来的加权概率解释是单独补充，没有把它算成分享对话中的第12轮。

轮次	原来的问题或关注点	在哪里接着读
1	与分解有关，为什么仍不能说破解必须先分解	第12章
2	已知有效私钥为什么能恢复因子	第8章
3	平方为1，为什么质数下只能是正负1	第8章、第13章
4	非平凡平方根为什么能用最大公约数分解	第8章
5	成功概率至少一半怎么证明	第9章到第11章
6	质数下的乘法群为什么循环	第5章、第14章
7	为什么编号和取幂后的结果仍均匀	第10章
8	为什么开始把指数对2的幂取模	第4章、第10章
9	怎样从均匀余数导出到达次数的概率	第10章
10	元素阶为什么整除群阶	第15章
11	阶为 $d$ 的元素为什么有 $φ (d)$ 个	第10章、第15章
补充	为什么求和后仍不超过一半	第11章

18.3 这次怎样改写，旧版怎样保留

第四版以一般推导为主，在符号出现时说明含义，在关键等式与推理之间说明依据。具体例子用于核对约分条件、指数周期、非平凡平方根与加权平均，不代替一般证明。第9—11章依次处理成功条件与独立性、均匀取幂与阶计数、加权概率上界。完整基础证明仍保留在第13—17章按问题回查。

此前版本均已归档。第三版见第三版HTML和第三版PDF。第二版的完整正文与检查材料保存在第二版HTML与第二版PDF所在目录。最早版本也保留：第一版HTML。

“欧拉函数”“欧拉定理”与复数里的欧拉公式 $e^{i θ} = \cos θ + i \sin θ$ 是不同内容；后者在代数基本定理笔记中阅读。原根和模质数的多项式，可接到多项式与分圆域笔记和伽罗瓦理论笔记。

配套Markdown与阅读索引保留。HTML 的正文、样式、公式、公式源码查看及复制工具都嵌入单文件，可以离线阅读；PDF 保留正文、矢量公式、带页码目录和分层书签。跨笔记和原对话链接需要对应文件，分享整套时保留目录层级。