密码学数学基础 笔记 6：从欧拉定理和费马小定理出发，理解模幂计算、费马素性测试、Carmichael 数、Miller-Rabin 测试与 Wilson 定理

费马、欧拉与素性测试

上一篇讨论了同余方程和中国剩余定理。这一篇继续研究可逆剩余类的幂和积，并把这些结构用于大整数计算与素性测试

欧拉定理与费马小定理

设 $a_1,\ldots,a_{\phi(m)}$ 是模 $m$ 的一个简化剩余系，也就是每个 $a_i$ 都与 $m$ 互素，且它们代表全部可逆剩余类。若 $\gcd(k,m)=1$，则乘以 $k$ 只会置换这些剩余类：

$$ka_1,\ldots,ka_{\phi(m)}$$

仍然是一个简化剩余系。于是比较置换前后的乘积：

$$\prod_{i=1}^{\phi(m)}ka_i \equiv\prod_{i=1}^{\phi(m)}a_i\pmod m$$

右侧的乘积与 $m$ 互素，可以约去，得到欧拉定理

$$\boxed{\gcd(k,m)=1\Longrightarrow k^{\phi(m)}\equiv1\pmod m}$$

当 $m=p$ 是素数时，$\phi(p)=p-1$，于是得到费马小定理

$$\boxed{p\text{ 为素数且 }p\nmid a\Longrightarrow a^{p-1}\equiv1\pmod p}$$

费马小定理也可以写成对所有整数都成立的形式

$$\boxed{a^p\equiv a\pmod p}$$

当 $p\mid a$ 时两边都为 $0$；当 $p\nmid a$ 时，把单位形式乘以 $a$ 即可得到它。例如不必展开 $2^{11}$，就能直接知道

$$11\mid(2^{11}-2)$$

素数条件不能省略。比如 $2^6=64\equiv4\pmod6$，并不等于 $2$。费马小定理还可以处理看起来不是整数的表达式。对

$$E(n)=\frac{n^5}{5}+\frac{n^3}{3}+\frac{7n}{15}$$

乘以 $15$ 后，只需证明 $3n^5+5n^3+7n$ 同时被 $3$ 和 $5$ 整除。由 $n^3\equiv n\pmod3$、$n^5\equiv n\pmod5$，有

$$3n^5+5n^3+7n\equiv0\pmod3,qquad 3n^5+5n^3+7n\equiv0\pmod5$$

因此 $15$ 整除分子，$E(n)$ 对每个整数 $n$ 都是整数

模幂与平方乘法

直接计算 $a^n$ 需要做 $n-1$ 次乘法，指数很大时不可行。模幂计算的关键是每一步都先取模，并把指数写成二进制

$$n=\sum_{i=0}^{\ell-1}n_i2^i,qquad n_i\in\{0,1\}$$

先不断平方得到

$$a^{2^0},a^{2^1},a^{2^2},\ldots$$

再把二进制位为 $1$ 的项相乘。整个过程只需要 $O(\ell)$ 次模乘法，其中 $\ell$ 是 $n$ 的二进制位数

例如 $35=2^5+2^1+2^0$，模 $35$ 计算 $2^{35}$ 时有

$$2^{2^0}\equiv2,\quad 2^{2^1}\equiv4,\quad 2^{2^5}\equiv11\pmod{35}$$

所以

$$\boxed{2^{35}\equiv11\cdot4\cdot2\equiv18\not\equiv2\pmod{35}}$$

这立即说明 $35$ 不是素数

从高位到低位扫描时，若当前已经读出的二进制前缀对应指数 $e$，追加一位 $b$ 后指数变成 $2e+b$，因此累积量按下面的方式更新

$$y\leftarrow y^2a^b\pmod m$$

从低位到高位扫描时，工作底数满足 $x_{i+1}\equiv x_i^2\pmod m$，遇到 $n_i=1$ 就把 $x_i$ 乘入累积量。两种写法都要求每一步及时约化，避免代表元无控制地增长

费马素性测试

若 $n$ 是素数，且 $a$ 不被 $n$ 整除，则费马小定理要求

$$a^{n-1}\equiv1\pmod n$$

因此反过来，如果某个底数满足

$$\gcd(a,n)=1,\qquad a^{n-1}\not\equiv1\pmod n$$

那么 $a$ 就是 $n$ 的一个合数见证，可以确定 $n$ 不是素数。测试通过只能说明它暂时没有被这个底数发现，不能反过来证明 $n$ 是素数

例如 $35$ 上取底数 $2$，平方乘法给出 $2^{35}\equiv18\pmod{35}$，等价地 $2^{34}\not\equiv1\pmod{35}$，所以 $2$ 是一个见证。这个测试对于随机候选数很有用，但面对专门构造的合数会出现假阳性

伪素数与 Carmichael 数

固定底数 $a$ 时，满足 $a^{n-1}\equiv1\pmod n$ 的合数称为关于该底数的费马伪素数。即使换用多个底数，也不能简单地认为通过测试就一定是素数，因为存在对所有互素底数都通过的合数

最小的例子是

$$561=3\cdot11\cdot17$$

它满足

$$2\mid560,\qquad10\mid560,\qquad16\mid560$$

对任意整数 $a$，若某个素因子 $p\in\{3,11,17\}$ 整除 $a$，则 $a^{561}\equiv a\equiv0\pmod p$。否则由费马小定理和 $p-1\mid560$，仍有 $a^{561}\equiv a\pmod p$。三个局部同余由中国剩余定理合并为

$$\boxed{a^{561}\equiv a\pmod{561}\qquad(\forall a\in\mathbb Z)}$$

满足这个性质的合数称为 Carmichael 数。Korselt 判据给出了一个实用刻画：合数 $n$ 是 Carmichael 数，当且仅当 $n$ 是奇数、无平方因子，并且对每个素因子 $p\mid n$ 都有 $p-1\mid n-1$

因此，费马测试的结论应当这样理解：失败可以证明合数，通过只能增加对素性的信心，不能单独给出确定证明

Miller-Rabin 测试

Miller-Rabin 测试利用了素数模数下平方根的限制。若 $p$ 是素数，则

$$x^2\equiv1\pmod p \Longrightarrow (x-1)(x+1)\equiv0\pmod p \Longrightarrow x\equiv\pm1\pmod p$$

也就是说，素数模下 $1$ 只有两个平方根。合数可能出现非平凡平方根，例如

$$19^2\equiv1\pmod{40},qquad19\not\equiv\pm1\pmod{40}$$

对奇数 $n>3$，写出

$$n-1=2^sd,qquad d\text{ 为奇数}$$

给定底数 $a$ 后，先计算 $x_0=a^d\pmod n$，再不断平方

$$x_{r+1}\equiv x_r^2\pmod n,\qquad0\le r<s$$

如果 $n$ 是素数，费马条件给出 $x_s=a^{n-1}\equiv1\pmod n$。沿着平方链向后分解

$$x_s-1=(x_{s-1}-1)(x_{s-1}+1)$$

可以看到，链条必须满足下面两种情况之一：

• $x_0\equiv1\pmod n$
• 某个 $0\le r<s$ 满足 $x_r\equiv-1\pmod n$

若两种情况都没有出现，底数 $a$ 就是 Miller-Rabin 见证，$n$ 必为合数

以 $n=41041$ 为例，

$$n-1=41040=2^4\cdot2565$$

取底数 $2$，平方链为

$$27994\longrightarrow27182\longrightarrow1\longrightarrow1\longrightarrow1\pmod{41041}$$

终点仍然是 $1$，所以简单的费马测试可能通过，但链中没有出现允许的 $-1$，而且 $27182$ 是非平凡的平方根，故 Miller-Rabin 测试判定 $41041$ 为合数

对固定的奇合数，独立均匀选择底数时，一轮 Miller-Rabin 测试误把合数判为“通过”的概率至多为 $1/4$。进行 $w$ 轮时有

$$\boxed{\Pr[\text{全部通过}\mid n\text{ 为合数}]\le4^{-w}}$$

这个量是条件概率上界，不是看到测试通过后合数的后验概率。对小于给定范围的整数，还可以使用已证明的固定底数集合，从而得到确定性的测试结果

Wilson 定理

费马和欧拉研究的是可逆剩余类的幂，Wilson 定理研究的是它们的乘积。若 $p$ 是素数，$1,2,\ldots,p-1$ 中每个数都有唯一的模 $p$ 逆元。把互为逆元的数配成一对，每一对的乘积都是 $1$

只有满足 $x^2\equiv1\pmod p$ 的数会留在配对之外。素数模下只有 $1$ 和 $-1$ 两个这样的数，因此

$$(p-1)! \equiv1\cdot(-1) \equiv-1\pmod p$$

这就是 Wilson 定理

$$\boxed{p\text{ 为素数}\Longrightarrow(p-1)!\equiv-1\pmod p}$$

反过来，对 $n>1$，同余 $(n-1)!\equiv-1\pmod n$ 也能推出 $n$ 是素数，所以它给出了一个素性判据。不过阶乘的计算远慢于平方乘法，Wilson 判据通常用于理论推导，而不是实际的大整数素性测试

在一般模数下，逆元配对仍然有效，但自逆元的数量可能超过两个。设

$$H=\{x\in(\mathbb Z/m\mathbb Z)^\times:x^2\equiv1\pmod m\}$$

当 $|H|=2$ 时，单位元的乘积为 $-1$；当 $|H|>2$ 时，额外的自逆元成组出现，单位元的乘积为 $1$。例如模 $8$ 时所有单位 $1,3,5,7$ 都是自逆元，乘积为 $1\pmod8$；模 $15$ 时

$$H=\{1,4,11,14\},qquad1\cdot4\cdot11\cdot14\equiv1\pmod{15}$$

逆元的两种计算方式

若 $\gcd(a,m)=1$，欧拉定理给出

$$a^{\phi(m)}\equiv1\pmod m$$

所以

$$a^{-1}\equiv a^{\phi(m)-1}\pmod m$$

当模数是已知素数 $p$ 时，可以进一步使用

$$a^{-1}\equiv a^{p-2}\pmod p$$

这两个公式都需要通过平方乘法计算幂。扩展欧几里得算法则直接构造逆元：若

$$au+mv=1$$

那么

$$\boxed{a^{-1}\equiv u\pmod m}$$

例如 $1=4\cdot14-5\cdot11$，所以 $4^{-1}\equiv14\equiv3\pmod{11}$。在模数已知、需要大量逆元时，扩展欧几里得通常更直接；若逆元运算本身昂贵，还可以先计算乘积的一个逆元，再用乘法恢复各个因子的逆元

对两个可逆元 $a,b$，令 $t=(ab)^{-1}$，则

$$\boxed{a^{-1}=tb,\qquad b^{-1}=ta}$$

这把两次求逆改成一次求逆和三次乘法，推广后就是批量求逆的基本方法

生成大素数

密码学中常用“随机生成候选数，再做素性测试”的方法寻找 $k$ 位素数。素数定理给出一个粗略估计：$k$ 位整数中成为素数的概率约为

$$\frac1{\ln(2^k)}=\frac1{k\ln2}$$

因此随机候选数平均尝试约 $k\ln2$ 次就会遇到一个素数。实际生成时通常只采样奇数，并使用带有明确错误概率或确定性范围保证的 Miller-Rabin 测试，而不能把一次费马测试通过当作素数证明