Fermat 测试
| 费马测试 | |
|---|---|
| 术语名称 | 费马测试 |
| 英语名称 | Fermat primality test |
| 别名 | 费马素性检验 |
Fermat 测试(Fermat primality test)是一种基于 Fermat 小定理的概率性质数测试/素性检验算法，用于快速判断一个给定的整数是否为质数。该算法对合数的判定是确定的，但对质数的判定存在一定的误判概率，可通过多次重复测试降低。
原理
根据 Fermat 小定理：若 [math]\displaystyle{ n }[/math] 是质数，且有与其互质的整数 [math]\displaystyle{ a }[/math] ，则 [math]\displaystyle{ a^{n-1} \equiv 1 \pmod{n} }[/math] 。 其逆否命题为：若存在一个与 [math]\displaystyle{ n }[/math] 互质的整数 [math]\displaystyle{ a }[/math] 使得 [math]\displaystyle{ a^{n-1} \not\equiv 1 \pmod{n} }[/math]，则 [math]\displaystyle{ n }[/math] 一定是合数。这也称为 [math]\displaystyle{ n }[/math] 的合数性的一个 Fermat 证据(Fermat witness for the compositeness of [math]\displaystyle{ n }[/math])。
Fermat 测试正是通过随机选取若干 [math]\displaystyle{ a }[/math] 并验证上述同余式，来探测 [math]\displaystyle{ n }[/math] 的合数性。
从原理中可以看出，当一个数在 Fermat 测试中使得同余式不成立时，它一定是一个合数；但是反过来不成立：使用 Fermat 测试进行筛选时，只能选择一定数量的 [math]\displaystyle{ a }[/math] 进行测试，一些合数可能刚好对所选择的质数成立；哪怕不限制测试的 [math]\displaystyle{ a }[/math] 的情况，仍然存在一些特殊的合数，无法通过 Fermat 测试判定为合数，称为 Fermat 伪质数或 Carmichael 数。
算法描述
伪代码
过程 Fermat测试
别名 fermat_test
参数 n, k : 正整数 // 待测数，测试轮数
返回 : 真假值 // 是否可能为质数（不保证）
循环 k 次
执行
随机选取 a ∈ [2, n-2] 且满足 gcd(a,n)=1
如果 a ^ₙ (n-1) ≠ 1 那么
结束子过程并返回 n 是合数
继续循环 k
返回 n 很可能是质数复杂度
每次测试的核心是计算模幂 [math]\displaystyle{ a^{n-1} \bmod n }[/math]，利用快速幂算法可在 [math]\displaystyle{ O(\log n) }[/math] 次模乘内完成，整体时间复杂度约为 [math]\displaystyle{ O(k \log^2 n \log\log n) }[/math]，其中 [math]\displaystyle{ k }[/math] 为测试轮数。
限制
- Fermat 伪素数：存在无穷多个合数 [math]\displaystyle{ n }[/math]，使得对所有与其互质的 [math]\displaystyle{ a }[/math] 都有 [math]\displaystyle{ a^{n-1} \equiv 1 \pmod{n} }[/math]。对此类合数，无论重复多少次 Fermat 测试，都无法识别其为合数。因此，实际应用中常将 Fermat 测试与 Miller–Rabin 测试等其他测试法结合，或直接使用更可靠的 Miller–Rabin 测试。
- 对于一般的合数，至少存在一半的 [math]\displaystyle{ a }[/math] 可作为证据，此时重复 [math]\displaystyle{ t }[/math] 次的错误概率 [math]\displaystyle{ \lt (1/2)^t }[/math]。