算法设计-02：数字算法

数字问题

两个外观相近的问题具有不同的已知复杂度：因数分解要求把 $N$ 写成素因子乘积，尚无已知经典多项式时间算法；素性判定只判断 $N$ 是否为素数，已有多项式时间算法。AKS 算法在 2002 年首次给出了无条件、确定性的多项式时间素性判定方法。大整数分解的困难性与 RSA 等公钥密码系统的安全分析密切相关，后文还会给出更具体的 RSA 单向性假设。

数字的表示

计算机用二进制表示数。进制越大表示越短，但换底只差常数因子。

例如十进制的 $1024$ 只写 4 位，二进制写作 $10000000000_2$ ，需要 11 位。两种记法的长度不同，但都与 $\log 1024$ 成正比。

位数：在 $b$ 进制下表示 $N\ge1$ 需 $\lfloor\log_bN\rfloor+1=\lceil \log_b(N+1)\rceil$ 位； $0$ 通常用一位表示。

换底公式： $\log_b N = \dfrac{\log_a N}{\log_a b}$ 。 $O$ 记号下底数无关，故数 $N$ 的规模统一记 $O(\log N)$ 。

数论算法的输入规模是位数 $O(\log N)$ ，而非数值 $N$ 本身。一个几百位的数，规模是几百，数值却是天文数字。

$\log N$ 还可从多种角度理解：它是得到 $N$ 所需的指数、把 $N$ 连续减半到 1 的次数、 $N$ 的二进制位数，以及含 $N$ 个结点的完全二叉树深度，以上说法只相差取整或常数因子。调和和 $1+1/2+\cdots+1/N$ 也为 $\Theta(\log N)$ 。

练习 1.31：计算 $N!=1\cdot2\cdots N$ 。

考查输入数值与输入位数的区别、结果长度，以及大整数乘法的位复杂度。

(a) 若 $N$ 是一个 $n$ 位二进制数， $N!$ 约需多少位？用 $\Theta$ 表示。

取阶乘中最大的 $\lfloor N/2\rfloor$ 个因子，得到

$\left(\frac N2\right)^{\lfloor N/2\rfloor}\le N!\le N^N.$

$\log_2(N!)=\Theta(N\log N).$

由于 $2^{n-1}\le N<2^n$ ，所需位数为 $\lfloor\log_2(N!)\rfloor+1=\Theta(n2^n)$ 。输出本身就比输入指数级地长。

(b) 给出计算 $N!$ 的算法并分析运行时间。

累乘过程的伪代码如下：
1
2
3
4
5
6
// 依次乘入所有因子，计算正整数 N 的阶乘。
function FACTORIAL(N):
    P ← 1
    for k ← 2 to N:
        P ← P × k
    return P
令 $P_1=1$ ，按 $P_k=kP_{k-1}$ （ $2\le k\le N$ ）依次相乘，返回 $P_N$ 。归纳可得 $P_k=k!$ 。第 $k$ 次乘法的两个数分别有 $\Theta(k\log k)$ 位和 $\Theta(\log k)$ 位；采用普通乘法，

$T(N)=\Theta\!\left(\sum_{k=2}^{N}k(\log k)^2\right).$

$T(N)=\Theta\!\left(N^2(\log N)^2\right) =\Theta(4^n n^2).$

保存当前乘积需要 $\Theta(N\log N)=\Theta(n2^n)$ 位空间。

加法

引理：任意三个单位数的和最多是两位数。

这是加法算法的基石。它在任意进制 $b \ge 2$ 都成立——三个最大单位数之和为 $3(b-1) \le b^2 - 1$ ，仍为两位数。二进制下三个单位比特之和最大为 3（即 11）。据此逐位相加、处理进位即可完成加法。

课件中的逐位例子是 $110101_2+100011_2=1011000_2$ ，即 $53+35=88$ 。每一列只需看两数的当前位与上一列进位，不必先转换成十进制。

复杂度：两个 $n$ 位数相加，和最多 $n+1$ 位，每位常数时间算出，总时间 $O(n)$ 。该算法最优：读入两个 $n$ 位数并写出答案就需 $\Omega(n)$ 次操作，故加法为 $\Theta(n)$ 。

CPU 一条指令能加 64 位内整数，但密码学常需处理几千位的数，此时必须回到逐位操作分析——即位复杂度（对单个比特的基本操作次数）。

乘法与除法

竖式乘法（grade-school）对两个 $n$ 位数生成 $n$ 行中间和，每行至多 $2n$ 位，共 $n$ 次 $O(n)$ 的加法，总复杂度 $O(n^2)$ 。

Quiz：一个 $n$ 位整数乘以 2 的复杂度是多少？

二进制下乘以 2 等于末尾补一个 $0$ 。若要显式写出 $n+1$ 位结果，仅输出就需 $\Theta(n)$ 时间；若只在固定字长寄存器上执行一次左移，指令数可以是常数。课件后续使用逐位操作的位复杂度，因此按 $O(n)$ 计入乘法递归的单层工作。

Al Khwarizmi 乘法。以 $11 \times 13$ 为例：

第一个数（减半）	第二个数（加倍）
11	13
5	26
2	52
1	104

规则：第一个数不断减半（向下取整），第二个数不断加倍，直到第一个数降到 1；划掉第一个数为偶数的行；剩余第二个数求和。 $13 + 26 + 104 = 143 = 11 \times 13$ 。本质是左边求第二个数的二进制表示，右边是相应移位——减半对应右移，加倍对应左移，划偶数行即筛出二进制位为 1 的项。

递归乘法 MULTIPLY：

$x \cdot y = \begin{cases} 2\left(x \cdot \lfloor y/2 \rfloor\right) & y \text{ 是偶数} \\ x + 2\left(x \cdot \lfloor y/2 \rfloor\right) & y \text{ 是奇数} \end{cases}$

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MULTIPLY}(x, y) \\[4pt] \hline \textbf{输入：}\ \text{两个 } n \text{ 位整数 } x \text{ 和 } y,\ y \ge 0 \\ \textbf{if}\ y = 0\ \textbf{then}\ \text{return}\ 0 \\ z = \text{MULTIPLY}(x, \lfloor y/2 \rfloor) \\ \textbf{if}\ y \text{ 是偶数}\ \textbf{then}\ \text{return}\ 2z \\ \textbf{else}\ \text{return}\ x + 2z \\ \hline \end{array}&& \end{aligned}$

把乘数 $y$ 的二进制逐位剥出—— $x \cdot y = 2(x \cdot \lfloor y/2 \rfloor)$ （偶数）或 $x + 2(x \cdot \lfloor y/2 \rfloor)$ （奇数），递归到底后逐步回代。每次调用 $y$ 减半，共 $n$ 次递归；每次做常数次操作（右移、判奇偶、左移、可能一次 $O(n)$ 加法），故总时间 $O(n^2)$ 。分治乘法（Karatsuba）可进一步降到 $O(n^{1.585})$ 。

除法同样用递归实现：

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：DIVIDE}(x, y) \\[4pt] \hline \textbf{输入：}\ \text{两个 } n \text{ 位整数 } x \text{ 和 } y,\ y \ge 1 \\ \textbf{if}\ x = 0\ \textbf{then}\ \text{return}(0, 0) \\ (q, r) = \text{DIVIDE}(\lfloor x/2 \rfloor, y) \\ q = 2q,\ r = 2r \\ \textbf{if}\ x \text{ 是奇数}\ \textbf{then}\ r = r + 1 \\ \textbf{if}\ r \ge y\ \textbf{then}\ r = r - y,\ q = q + 1 \\ \text{return}(q, r) \\ \hline \end{array}&& \end{aligned}$

逐位恢复商与余数。先递归求 $\lfloor x/2 \rfloor$ 的商余，再翻倍并“塞回”被移走的最低位（奇数则 $r$ 加 1），最后若余数超界则减 $y$ 、商加 1。

正确性可由递归不变量说明。设递归结果满足

$\left\lfloor\frac x2\right\rfloor=qy+r, \qquad 0\le r<y.$

翻倍并补回 $x$ 的最低位 $b=x\bmod2$ 后，得到 $x=(2q)y+(2r+b)$ ，且 $0\le2r+b<2y$ 。因此至多减一次 $y$ 就能使余数重新落入 $[0,y-1]$ ，同时相应地把商加 1。递归深度为 $O(n)$ ，每层比较、加减和移位最多处理 $O(n)$ 位，故普通位运算模型下总时间为 $O(n^2)$ ，递归栈为 $O(n)$ 。

例如 DIVIDE $(13,3)$ 会先处理 $13\to6\to3\to1\to0$ ，再逐层补回二进制最低位，最终得到商 $4$ 、余数 $1$ ，满足 $13=4\cdot3+1$ 。

模运算

模运算处理有限范围整数。 $x \bmod N$ 是 $x$ 除以 $N$ 的余数：若 $x = qN + r$ 且 $0 \le r < N$ ，则 $x \bmod N = r$ 。 $x \equiv y \pmod N$ （同余）指两者相差 $N$ 的整数倍，即 $N \mid (x - y)$ 。模运算有两种理解：限制范围（越界回绕，如钟表），或把整数划分为 $N$ 个等价类 $\{i + kN \mid k \in \mathbb{Z}\}$ 。

模运算的典型例子是补码： $n$ 位补码表示 $[-2^{n-1}, 2^{n-1}-1]$ ，非负数用普通二进制（首位 0）；负数 $-x$ 先写出正数 $x$ 的 $n$ 位二进制，再逐位取反并加 1（首位 1）。例如 8 位的 $5$ 是 $00000101$ ，取反加 1 得 $11111011$ ，它作为无符号数是 $251$ ，而 $251\equiv-5\pmod{256}$ 。由此可见，补码加法与模 $2^8$ 加法使用相同的比特运算。

替换规则：若 $x \equiv x' \pmod N$ 且 $y \equiv y' \pmod N$ ，则

$\begin{aligned} x+y&\equiv x'+y'\pmod N,\\ xy&\equiv x'y'\pmod N. \end{aligned}$

另有结合律、交换律、分配律。核心结论：任意中间步骤都可归约到模 $N$ 的余数，使每次归约后的数都落在 $[0,N-1]$ 。

例如利用 $2^5=32\equiv1\pmod{31}$ ，可直接化简

$2^{345}=(2^5)^{69}\equiv32^{69}\equiv1^{69}\equiv1\pmod{31}.$

三种模运算的复杂度：模加法 $x, y \in [0, N-1]$ ，和超界减 $N$ 即可， $O(n)$ ；模乘法乘积最大 $(N-1)^2$ （约 $2n$ 位），乘后取余即一次除法， $O(n^2)$ ；模除法仅当除数与 $N$ 互质时合法，可在 $O(n^3)$ 完成（见后）。

模幂

密码系统中需计算 $x^y \pmod N$ ，其中 $x, y, N$ 均几百位。结果只几百位，但 $x^y$ 可能上千万位（ $x, y$ 仅 20 位时）。朴素法反复乘 $x$ 并取余需 $y$ 次乘法， $y$ 有 500 位时不可行。

快速幂（反复平方）：从 $x$ 出发反复平方：

$x \bmod N \to x^2 \bmod N \to x^4 \bmod N \to x^8 \bmod N \to \cdots \to x^{2^{\lfloor \log y \rfloor}} \bmod N$

每步 $O(\log^2 N)$ ，共 $\log y$ 次乘法。求 $x^y$ 只需把 $y$ 二进制中为 1 的幂相乘： $x^{25} = x^{11001_2} = x^{16} \cdot x^8 \cdot x^1$ 。递归形式：

$x^y \bmod N = \begin{cases} \left(x^{\lfloor y/2 \rfloor}\right)^2 \bmod N & y \text{ 是偶数} \\ x \left(x^{\lfloor y/2 \rfloor}\right)^2 \bmod N & y \text{ 是奇数} \end{cases}$

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MODEXP}(x, y, N) \\[4pt] \hline \textbf{输入：}\ \text{两个 } n \text{ 位整数 } x,N,\ N\ge2;\ \text{非负整数指数 } y \\ \textbf{if}\ y = 0\ \textbf{then}\ \text{return}\ 1 \\ z = \text{MODEXP}(x, \lfloor y/2 \rfloor, N) \\ \textbf{if}\ y \text{ 是偶数}\ \textbf{then}\ \text{return}\ z^2 \bmod N \\ \textbf{else}\ \text{return}\ x \cdot z^2 \bmod N \\ \hline \end{array}&& \end{aligned}$

与递归乘法同构，都是“减半后平方/倍乘”——把指数 $y$ 的二进制逐位剥出， $y$ 偶则 $x^y = (x^{y/2})^2$ ，奇则 $x^y = x(x^{y/2})^2$ 。若 $y$ 有 $m$ 位，就递归 $O(m)$ 层，每层进行常数次 $n$ 位模乘，总时间为 $O(mn^2)$ ；当指数也至多 $n$ 位时，得到课件给出的 $O(n^3)$ 。未经取模的 $x^y$ 可能有 $\Theta(y\log x)$ 位，快速幂只需处理指数的 $\Theta(\log y)$ 个二进制位。

练习 1.14：怎样高效计算第 $n$ 个斐波那契数 $F_n$ 模整数 $p$ 的余数？提示使用矩阵方法。

本题考查第一讲的斐波那契递推、模运算替换规则，以及本节的二进制快速幂。令

$A=\begin{pmatrix}0&1\\1&1\end{pmatrix}.$

$A^n\begin{pmatrix}0\\1\end{pmatrix} =\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}.$

$n=0$ 时等式成立；若在 $n$ 时成立，左乘 $A$ 就得到下一项，因此归纳可证。于是只需计算 $A^n\bmod p$ ，再取其与 $(0,1)^T$ 乘积的第一项。若 $p=1$ ，答案直接为 $0$ 。

当 $p\ge2$ 时，初始化 $R=I$ 、 $B=A\bmod p$ 、 $e=n$ 。每轮若 $e$ 为奇数，先令 $R\leftarrow RB\bmod p$ ；随后令 $B\leftarrow B^2\bmod p$ 、 $e\leftarrow\lfloor e/2\rfloor$ 。不变量是 $RB^e\equiv A^n\pmod p$ ，因此循环结束时 $R\equiv A^n\pmod p$ 。

伪代码如下，矩阵下标从 $1$ 开始；乘法为矩阵乘法，取模作用于每个元素。由于 $R(0,1)^T$ 的第一项为 $R[1,2]$ ，可直接返回该元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
// 用矩阵快速幂计算 F_n mod p；输入 n ≥ 0，p ≥ 1。
function FIBONACCI-MOD(n, p):
    if p = 1:
        return 0
    R ← [[1, 0], [0, 1]]
    B ← [[0, 1], [1, 1]]
    e ← n
    while e > 0:
        if e mod 2 = 1:
            R ← (R × B) mod p
        B ← (B × B) mod p
        e ← floor(e / 2)
    return R[1, 2]
每轮处理指数的一位，执行 $O(\log(n+2))$ 轮。矩阵规模固定，元素均可约到 $[0,p-1]$ ，用普通乘法时位复杂度为 $O\!\left(\log(n+2)(\log p)^2\right)$ 。

欧几里得算法

问题：求 $\gcd(x, y)$ 。

欧几里得规则：若 $x, y$ 是正整数且 $x \ge y$ ，则

$\gcd(x, y) = \gcd(x \bmod y, y)$

证明：只需证 $\gcd(x, y) = \gcd(x - y, y)$ （ $x \bmod y$ 是 $x$ 反复减 $y$ 的结果）。任何同时整除 $x$ 和 $y$ 的数也整除 $x - y$ ，反之亦然，故两边公约数集合相同，最大公约数相等。

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：EUCLID}(x, y) \\[4pt] \hline \textbf{输入：}\ \text{两个整数 } x \text{ 和 } y \text{，} x \ge y \ge 0 \\ \textbf{if}\ y = 0\ \textbf{then}\ \text{return}\ x \\ \text{return}\ \text{EUCLID}(y, x \bmod y) \\ \hline \end{array}&& \end{aligned}$

不断用"取余"替换较大的数，直到 $y = 0$ 时返回 $x$ ，每一步都缩小规模并收敛到 gcd。复杂度依赖关键引理：

引理：若 $a \ge b > 0$ ，则 $a \bmod b < a/2$ 。

证明：若 $b \le a/2$ ，则 $a \bmod b < b \le a/2$ ；若 $b > a/2$ ，则 $a \bmod b = a - b < a/2$ 。两种情况均成立。

由此每连续两轮参数至少减半一次，即长度至少缩一位。初始 $n$ 位整数， $2n$ 次递归内到达基例；每次调用做一次 $O(n^2)$ 除法，故总时间 $O(n^3)$ 。

扩展欧几里得算法：如何验证 $d$ 是 $\gcd(x, y)$ ？仅验证 $d$ 整除 $x, y$ 不够（ $d$ 可能只是某个公约数）。

引理：若 $d$ 同时整除 $x$ 和 $y$ ，且 $d = ax + by$ 对某整数 $a, b$ 成立，则 $d = \gcd(x, y)$ 。

证明： $d$ 是公约数，故 $d \le \gcd(x, y)$ ；反过来 $\gcd(x, y)$ 整除 $x, y$ ，也整除 $ax + by = d$ ，故 $\gcd(x, y) \le d$ 。两边夹逼得 $d = \gcd(x, y)$ 。

故若能找到 $a, b$ 使 $d = ax + by$ ，即得到 gcd：

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：EXTENDED-EUCLID}(x, y) \\[4pt] \hline \textbf{输入：}\ \text{两个整数 } x \text{ 和 } y \text{，} x \ge y \ge 0 \\ \textbf{if}\ y = 0\ \textbf{then}\ \text{return}(1, 0, x) \\ (x', y', d) = \text{EXTENDED-EUCLID}(y, x \bmod y) \\ \text{return}(y', x' - \lfloor x/y \rfloor y', d) \\ \hline \end{array}&& \end{aligned}$

返回三元组 $(a, b, d)$ 使 $ax + by = d = \gcd(x, y)$ 。核心是递归回代——已知 $x'y + y'(x \bmod y) = d$ ，代入 $x \bmod y = x - \lfloor x/y \rfloor y$ ，再整理出关于 $x, y$ 的线性组合。

其正确性可用归纳法证明。基例 $y=0$ 返回 $(1,0,x)$ ，满足 $1\cdot x+0\cdot y=x=\gcd(x,0)$ 。递归层设

$x'y+y'(x\bmod y)=d.$

代入 $x\bmod y=x-\lfloor x/y\rfloor y$ ，得到

$y'x+\left(x'-\left\lfloor\frac xy\right\rfloor y'\right)y=d,$

恰好对应返回的两个系数；欧几里得规则又保证 $d=\gcd(x,y)$ 。递归深度与普通欧几里得算法相同，因此在讲义采用的普通除法模型下时间为 $O(n^3)$ 。

模逆与模除法

模逆：若 $ax \equiv 1 \pmod N$ ，则 $x$ 是 $a$ 模 $N$ 的乘法逆元 $a^{-1}$ ，模 $N$ 至多一个。逆元不一定存在，如 $2$ 模 $6$ 不可逆。

引理：若 $\gcd(a, N) > 1$ ，则 $ax \not\equiv 1 \pmod N$ 对任意 $x$ 。

证明：由带余除法， $ax$ 除以 $N$ 得商 $q$ 与余数 $r = ax \bmod N$ ，即 $ax = qN + r$ ，故

$ax \bmod N = ax - qN$

$\gcd(a, N)$ 同时整除 $ax$ 与 $qN$ （它整除 $a$ 与 $N$ ，故整除它们的任意倍数），因而也整除两者的差 $ax - qN = ax \bmod N$ 。也就是说，余数 $ax \bmod N$ 一定是 $\gcd(a, N)$ 的整数倍。若 $\gcd(a, N) > 1$ ，这个余数可能是 $0$ 或不小于 $2$ 的倍数，但不可能等于 $1$ ，故 $ax \not\equiv 1 \pmod N$ 。

反之若 $\gcd(a, N) = 1$ ，扩展欧几里得给出 $ax + Ny = 1$ ，即 $ax \equiv 1 \pmod N$ ——此 $x$ 即逆元。

定理（模除法）： $a$ 有模 $N$ 的乘法逆元，当且仅当 $a$ 与 $N$ 互质；逆元存在时可用扩展欧几里得算法在 $O(n^3)$ 内求出。

故模 $N$ 下只能除以与 $N$ 互质的数，而"除法"实为乘以逆元。

练习 1.20：分别求下列乘法逆元；若不存在，说明原因。

本题考查扩展欧几里得算法、贝祖等式，以及“存在逆元当且仅当与模数互质”。

(a) 求 $20$ 模 $79$ 的逆元。

$79=3\cdot20+19,\ 20=19+1$ ，回代得 $1=4\cdot20-79$ ，所以 $20^{-1}\equiv4\pmod{79}$ 。

(b) 求 $3$ 模 $62$ 的逆元。

$62=20\cdot3+2,\ 3=2+1$ ，回代得 $1=21\cdot3-62$ ，所以 $3^{-1}\equiv21\pmod{62}$ 。

© 求 $21$ 模 $91$ 的逆元。

$91=4\cdot21+7,\ 21=3\cdot7$ ，故 $\gcd(21,91)=7$ ，逆元不存在。

(d) 求 $5$ 模 $23$ 的逆元。

$23=4\cdot5+3,\ 5=3+2,\ 3=2+1$ ，回代得 $1=14\cdot5-3\cdot23$ ，所以 $5^{-1}\equiv14\pmod{23}$ 。

本讲各基本运算的复杂度汇总（输入规模为位数 $n = O(\log N)$ ）：

运算	复杂度	说明
加法	$O(n)$	最优，下界 $\Omega(n)$
乘法	$O(n^2)$	竖式 / 递归；可优化到 $O(n^{1.585})$
除法	$O(n^2)$	递归逐位恢复商和余数
模加法	$O(n)$	一次加法，至多再减一次 $N$
模乘法	$O(n^2)$	普通乘法后取余
模幂	$O(n^3)$	指数也至多 $n$ 位时，反复平方 + 二进制分解
最大公约数	$O(n^3)$	欧几里得算法
模逆 / 模除法	$O(n^3)$	扩展欧几里得算法；仅对互质除数合法

费马小定理

费马小定理是素数判定与 RSA 密码系统的理论基础。

定理（费马小定理）：若 $p$ 是素数，则对任意 $1 \le a < p$ ，有 $a^{p-1} \equiv 1 \pmod p$ 。

证明：设 $S = \{1, 2, \dots, p-1\}$ 。将 $S$ 中每个数乘以 $a$ 再取模 $p$ ，得到的集合 $\{a \cdot 1 \bmod p, a \cdot 2 \bmod p, \dots, a \cdot (p-1) \bmod p\}$ 恰好是 $S$ 的一个排列——因为 $a \cdot i \bmod p$ （ $i \in S$ ）两两不同（若 $a \cdot i \equiv a \cdot j \pmod p$ 且 $i \ne j$ ，则 $p \mid a(i-j)$ ，与 $p$ 是素数且 $p \nmid a$ 、 $|i-j| < p$ 矛盾），且都不为 0。于是两边元素乘积相等：

$(p-1)! \equiv a^{p-1} \cdot (p-1)! \pmod p$

两边消去 $(p-1)!$ （与 $p$ 互质），得 $a^{p-1} \equiv 1 \pmod p$ 。

素数测试

费马小定理给出素数的一个必要条件，据此可设计素数测试：

$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：PRIMALITY}(N) \\[4pt] \hline \textbf{输入：}\ \text{整数 } N\ge2 \\ \text{随机选取正整数 } a < N \\ \textbf{if}\ a^{N-1} \equiv 1 \pmod N\ \textbf{then}\ \text{return}\ \text{yes} \\ \textbf{else}\ \text{return}\ \text{no} \\ \hline \end{array}&& \end{aligned}$

问题在于费马定理不是充要条件：存在合数 $N$ 满足 $a^{N-1} \equiv 1 \pmod N$ 。例如 $341 = 11 \times 31$ ，却有 $2^{340} \equiv 1 \pmod{341}$ 。更糟的是卡迈克尔数：

定理（卡迈克尔数）：存在合数 $N$ ，使得对所有与 $N$ 互质的 $a < N$ 都有 $a^{N-1} \equiv 1 \pmod N$ 。

例： $561 = 3 \times 11 \times 17$ 就是卡迈克尔数，此时所有与 $561$ 互质的底数都会通过费马测试。

对非卡迈克尔数，费马测试的可靠性有保证：

引理：若对某个与 $N$ 互质的 $a$ 有 $a^{N-1} \not\equiv 1 \pmod N$ ，则至少一半的 $a < N$ 会不通过该测试。

证明：固定一个不通过的 $a$ 。考察函数 $b \mapsto a \cdot b \bmod N$ ——它是一一对应的（ $a$ 与 $N$ 互质，存在逆元），因此每个通过的 $b$ 都对应一个不通过的 $a \cdot b$ （因为 $(a \cdot b)^{N-1} = a^{N-1} b^{N-1} \not\equiv b^{N-1} \equiv 1$ ），故不通过的个数至少与通过的一样多。

暂时排除卡迈克尔数后，可以断言： $N$ 为素数时所有 $a$ 都通过； $N$ 为合数时至多一半的 $a$ 通过。即

$\Pr(\text{yes}\mid N\text{ 为素数})=1, \qquad \Pr(\text{yes}\mid N\text{ 为非卡迈克尔合数})\le\frac12.$

独立随机选择 $a_1,\ldots,a_k<N$ ，仅当所有底数都通过时才返回 yes，便得到 PRIMALITY2。对非卡迈克尔合数，其单侧错误概率至多为 $2^{-k}$ 。例如取 $k=10$ 时，这个上界是 $1/1024$ 。这个界不能直接用于卡迈克尔数；费马测试只能给出“发现证据即可确认是合数”的筛查方法，处理任意输入还需使用能够避开此缺陷的素性测试。讲义开头提到的 AKS 是确定性方案。

练习 1.35：威尔逊定理断言，对 $N\ge2$ ， $N$ 为素数当且仅当 $(N-1)!\equiv-1\pmod N$ 。

本题考查模逆、素数模下的消去律、最大公约数，以及数值 $N$ 与输入位数 $\log N$ 的区别。

(a) 若 $p$ 为素数，哪些 $1\le x<p$ 是自己的模 $p$ 逆元？

$x^{-1}\equiv x\pmod p$ 等价于 $(x-1)(x+1)\equiv0\pmod p$ 。因为 $p$ 是素数， $x\equiv1$ 或 $x\equiv-1\pmod p$ 。所以答案是 $1$ 和 $p-1$ ； $p=2$ 时两者相同。

(b) 将逆元两两配对，证明 $(p-1)!\equiv-1\pmod p$ 。

当 $p>2$ ，除 $1$ 、 $p-1$ 外，其余元素与各自不同的逆元两两配对，每对乘积模 $p$ 为 $1$ 。因此 $(p-1)!\equiv1\cdot(p-1)\equiv-1\pmod p$ 。当 $p=2$ ， $1!\equiv-1\pmod2$ 也成立。

© 证明合数 $N$ 不满足 $(N-1)!\equiv-1\pmod N$ 。

若 $N$ 为合数，取真因子 $1<a<N$ 。由于 $a\mid N$ 且 $a\mid(N-1)!$ ，有 $\gcd(N,(N-1)!)\ge a>1$ ；但若 $(N-1)!\equiv-1\pmod N$ ，这个最大公约数必须是 $1$ ，矛盾。这里须排除 $N=1$ ：模 $1$ 时同余式成立，但 $1$ 不是素数。

(d) 既然这是素数的充要条件，为什么不能直接据此得到高效的素数测试？

直接计算 $(N-1)!\bmod N$ 需要 $N-1$ 次模乘。若 $N$ 有 $n$ 位，则 $N=\Theta(2^n)$ ，普通位运算实现约需 $O(2^n n^2)$ 时间，随输入位数指数增长。

随机素数生成

定理（素数定理）：设 $\pi(x)$ 为不超过 $x$ 的素数个数，则 $\pi(x) \sim \frac{x}{\ln x}$ ，即 $\lim_{x\to\infty} \frac{\pi(x)}{x/\ln x} = 1$ 。

素数分布足够密集，因此可反复随机取 $n$ 位数 $N$ 并做素数测试，通过则输出，否则重试。对充分大的 $n$ ，每轮抽到真正素数的概率为 $\Theta(1/n)$ ；若所用测试总能接受素数，平均 $O(n)$ 轮便会遇到素数。若只用上文的费马测试，“通过”仍可能是合数，特别是卡迈克尔数，因此这个过程还不能保证输出一定为素数。

上述素数测试属于随机算法，分两类：

Monte Carlo 算法：运行时间有界，正确性随机。例：素数测试。
Las Vegas 算法：一定正确，运行时间随机（以较大概率较快）。例：快速排序、哈希。

密码学

密码学的典型场景：Alice 想向 Bob 私密发送消息 $x$ （二进制）。Alice 用加密函数 $e$ 编码为 $e(x)$ 发送，Bob 用解密函数 $d$ 解码得 $d(e(x)) = x$ 。窃听者 Eve 截获 $e(x)$ ，入侵者 Ida 甚至可冒充 Alice 或 Bob。

私钥与公钥：传统密码学基于私钥协议——Alice 和 Bob 事先见面约定密码本。而公钥协议允许 Alice 给素未谋面的 Bob 发消息：Bob 造一把"数字锁"公开，只有他有钥匙。

一次性密码本（One-Time Pad）：Alice 和 Bob 秘密共享与消息等长的随机二进制串 $r$ ，加密为按位异或 $e_r(x) = x \oplus r$ 。 $e_r$ 是双射且是自身的逆： $e_r(e_r(x)) = (x \oplus r) \oplus r = x$ 。当 $r$ 均匀随机、保持秘密且只使用一次时，Eve 截获 $y = x \oplus r$ 得不到 $x$ 的任何信息。但 $r$ 不可重复使用：若用同一 $r$ 加密两条消息 $x, z$ ，则知道 $x \oplus r$ 和 $z \oplus r$ 即可推出 $x \oplus z$ ，暴露两者相同的前缀、后缀或可猜测结构。随机串需覆盖所有消息的总长度，生成和分发成本很高。

AES 是可重复使用密钥的现代分组密码标准，分组长度固定为 128 位。其安全性仍依赖正确的工作模式、随机数和密钥管理，不能把“底层密码算法难以破解”等同于整个通信过程安全。

RSA 密码系统的核心性质：选两个不同的素数 $p, q$ ，令 $N = pq$ 。

RSA 基本性质：对任意与 $(p-1)(q-1)$ 互质的 $e$ ，映射 $x \mapsto x^e \bmod N$ 是 $\{0, 1, \dots, N-1\}$ 上的双射；其逆由 $d$ 给出，其中 $d$ 是 $e$ 模 $(p-1)(q-1)$ 的逆元，即 $(x^e)^d \equiv x \pmod N$ 。

证明： $e$ 与 $(p-1)(q-1)$ 互质，故模 $(p-1)(q-1)$ 可逆。 $ed \equiv 1 \pmod{(p-1)(q-1)}$ ，即 $ed = 1 + k(p-1)(q-1)$ 。模 $p$ 考察 $x^{ed}$ ：若 $p\mid x$ ，则 $x^{ed}\equiv x\equiv0\pmod p$ ；若 $p\nmid x$ ，由费马小定理 $x^{p-1}\equiv1\pmod p$ ，所以

$x^{ed}=x\left(x^{p-1}\right)^{k(q-1)}\equiv x\pmod p.$

模 $q$ 同理。由于不同素数 $p,q$ 互质， $p$ 与 $q$ 都整除 $x^{ed}-x$ ，故 $pq=N$ 整除它，即 $(x^e)^d\equiv x\pmod N$ 。这也证明了加密映射存在逆映射，因而是双射。

RSA 协议：Bob 选两个 $n$ 位随机素数 $p, q$ ，公钥为 $(N, e)$ （ $N = pq$ ， $e$ 是与 $(p-1)(q-1)$ 互质的 $2n$ 位数），私钥为 $d = e^{-1} \bmod (p-1)(q-1)$ 。Alice 查公钥 $(N, e)$ ，发送 $y = x^e \bmod N$ ；Bob 计算 $y^d \bmod N$ 解密。

用小数验证流程：取 $p=5,q=11$ ，则 $N=55$ 、 $(p-1)(q-1)=40$ 。选 $e=3$ ，其模 40 的逆元为 $d=27$ ，因为 $3\cdot27=81\equiv1\pmod{40}$ 。若消息 $x=7$ ，密文为 $y=7^3\bmod55=13$ ；Bob 计算 $13^{27}\bmod55=7$ ，恢复原消息。这个例子只展示代数正确性，小素数不能用于实际保密通信。

安全性假设：给定 $N, e$ 和 $y = x^e \bmod N$ ，确定 $x$ 在计算上不可行。Eve 穷举 $x$ 需指数时间；分解 $N$ 得到 $p, q$ 再求 $d$ 也因分解困难而不可行。

数字签名用于证明消息真实性，含两个算法：签名算法（给定消息和私钥产生签名）与验证算法（给定消息、公钥和签名，接受或拒绝）。

协议安全

密码算法本身难以破解，并不保证组合它们的通信协议安全。Needham-Schroeder 公钥协议（NSPK）展示了身份信息与随机数绑定不充分时的中间人攻击。记 $\{M\}_{+K_X}$ 为使用 $X$ 的公钥加密消息 $M$ ， $N_A,N_B$ 为双方各自产生的一次性随机数。原协议为

$\begin{aligned} A\to B &: \{A,N_A\}_{+K_B},\\ B\to A &: \{N_A,N_B\}_{+K_A},\\ A\to B &: \{N_B\}_{+K_B}. \end{aligned}$

第一步使 $B$ 得到 $A$ 的身份和挑战值 $N_A$ ；第二步回传 $N_A$ 证明响应与本次会话相关，同时用 $N_B$ 挑战 $A$ ；第三步回传 $N_B$ 。然而，第二条消息没有写明响应者身份。攻击者 $I$ 可利用 Alice 主动与自己建立的会话，把消息转发给 Bob：

$\begin{aligned} A\to I &: \{A,N_A\}_{+K_I},\\ I(A)\to B &: \{A,N_A\}_{+K_B},\\ B\to I(A) &: \{N_A,N_B\}_{+K_A},\\ I\to A &: \{N_A,N_B\}_{+K_A},\\ A\to I &: \{N_B\}_{+K_I},\\ I(A)\to B &: \{N_B\}_{+K_B}. \end{aligned}$

$I(A)$ 表示 $I$ 冒充 $A$ 。攻击者不能解开 Bob 发出的第二条消息，却可原样转交给 Alice。Alice 误以为该消息属于自己与 $I$ 的会话，解密后把 $N_B$ 用 $I$ 的公钥发回； $I$ 因而获得 $N_B$ ，再向 Bob 完成认证。最终 Bob 错误地相信正在与 Alice 通信。

修复方法是在第二条消息中加入 Bob 的身份，使响应与具体通信方绑定：

$\begin{aligned} A\to B &: \{A,N_A\}_{+K_B},\\ B\to A &: \{B,N_A,N_B\}_{+K_A},\\ A\to B &: \{N_B\}_{+K_B}. \end{aligned}$

若攻击者再次转发消息，Alice 会在解密结果中看到身份 $B$ ，而不是当前会话预期的 $I$ ，于是终止协议。这说明协议验证不仅要检查加密是否正确，还要检查消息的身份、方向和会话上下文是否被完整绑定。