假证人 – 搞英语 → 看世界

匹诺曹与法官交谈

费马素数检验

费马小定理指出，如果p是素数，且a不是p的倍数，则

p ⁻¹ = 1 ( 模p )。

费马小定理的逆否命题是说

a ^{p −1} ≠ 1 (mod p )

那么要么p不是素数，要么a是p的倍数。逆否命题用于判断一个数是否为素数。取一个小于p的数a （因此a显然不是p的倍数），计算a ^{p −1} mod p 。如果结果与 1 mod p不一致，则p不是素数。

因此，费马小定理为我们提供了一种证明一个数是合数的方法：如果p ^-1模p等于 1 以外的任何数，则 p肯定是合数。但如果p ^-1模p等于 1，则该检验无定论。这样的结果暗示p是素数，但也可能不是。

例如，假设我们要测试 57 是否为素数。如果我们使用费马素数测试法，令a = 2，我们会发现 57 不是素数，如下面 Python 代码所示。

 >>> pow(2, 56, 57)     4

现在让我们使用a = 64 来测试 91 是否为素数。那么费马测试结果是不确定的。

 >>> pow(64, 90, 91)     1

事实上 91 不是质数，因为它是 7 × 13 的因数。

如果我们以a = 2 作为基数，就能证明 91 是合数。实际应用中，费马检验法会应用多个a值（如有必要）。

如果a ^{p −1} = 1 (mod p )，那么a就是p为素数的证明。这虽然不是证明，但却是证据。p 仍然可能不是素数，在这种情况下，a是对p为素数的伪证明，或者p是底数a的伪素数。在上面的例子中，64 是对 91 为素数的伪证明。

直到最近偶然读到一篇论文 [1]，我才意识到合数平均而言有很多伪证。当N很大时，小于N的合数的平均伪证数量大于N ^15/23 。虽然N ^15/23很大，但相对于N来说还是小的。

然而，如果你随机选择一个基数a ，那么你挑选出其中一个假证人的机会很小，因此基于费马小定理的概率素数测试是实用的，实际上也很常见。

请注意，上面引用的结果是对虚假证人数量的下限。如果你想保证你不太可能意外遇到虚假证人，那么你确实需要一个上限。[1] 中的作者确实给出了上限，但它们的表达式比下限复杂得多。

[1] Paul Erdős 和 Carl Pomerance。《论合数的伪证数量》。《计算数学》。第 46 卷，第 173 期（1986 年 1 月），第 259-279 页。