云风的 BLOG

说道素数检验法，最基本的方法就是按素数的定义，拿这个整数去除比它小的所有大于 2 的整数，看是否全部不能整除。当然，我们可以做一些明显的优化：只用去除比它平方根小的数字，如果可能，尽量选取素数（剔除明显不必测试的数字，比如偶数）。

再进一步，我们可以运用费马小定理：即，对于一个素数 p，取任何一个整数 a ， a^p 对 p 取模一定为 a 。若 a 不是 p 的倍数的话，这等价于 a ^ (p-1) 对 p 取模为 1 。

这个定理有非常多的证明方法，用数学归纳法证明最容易理解 。这肯定没超过中学的数学知识。

我们可以采用费马小定理去测试一个数字是否为素数：任取整数 a ，测试 p 。如果 a ^ (p-1) 对 p 取模不为 1 ，那 p 就不是素数，反之，它有一定概率是一个素数。

如果我们不断的选择不同的 a 去测试 p ，只要有一个 a 能证明 p 不是素数它就不是，反之，测试的 a 越多，p 就越可能是素数。

如果 p 通过了费马小定理的检验，它是素数的概率不算特别高。如果我们能找到一个改进的算法，可以让概率提升会更好。 米勒拉宾素数检验法就是对费马小定理检验法的一个改进。它可以让一个合数更难通过检验，同时，特别适合计算机计算（单次检验的计算复杂度较费马小定理检验并没有太大的提升）。

这个算法可以这样表述：假设一个整数 p 是一个大于 2 的素数，那么 p - 1 就是一定是一个偶数，可以表示为 2^s * d 的形式，其中 d 为一个奇数。换句话说，我们可以把 p - 1 的 2 因子都提取出来。

此时，对于任何比 p 小的整数 a ， 以下两个形式之一必然成立：

1. a ^ d 对 p 取模为 1 。
2. a ^ (2^r * d) 对 p 取模为 -1 。（r 为 0 到 s-1 之间的某个整数）

反之，如果 p 是一个合数，我们任取一个 a ，带入上面的式子去计算，一定全部不成立。若通过这一系列计算可以证明 p 是一个合数，就可以把 a 称为 p 是合数的一个凭证 (witness) 。若 a 不能证明 p 是一个合数，那么它就有极大概率是一个素数。

让我们随机选取 a ，多次检验 p ，要么很快的证明 p 是一个合数，要么知道 p 是素数的概率非常大。

虽然这是个随机化算法，但是如果 p 的范围有限，比如在计算机中一定能放入一个字长中，那么我们就能事先找到一组合适的 a ，100% 确定 p 是否是素数。

例如，如果 p 是一个 32 位整数，我们只要选取 { 2, 7, 61 } 三个凭据，依次测试 p ，如果 p 全部通过，就能确定 p 一定是素数；如果把 p 放宽到 64 位整数，则需要七个特定的数字。这一点一定能被证明（因为数字集是有限的）。

对于特定范围的整数，找到更合适的凭据集是个有意义的工作 。在这个网站上列出了目前的成果。

另外一个很容易想到的进一步优化是对需要检验的整数集做依次 hash ，散列到若干更小的集合中，对每个集合就只需要选取更少数量的凭据即可。例如，对于 32 bit 整数，我们用一个简单的 hash 算法，散列到 1024 个子集中，每个子集就只有 22bit 个整数，这样的集合只需要一次检验就够了。这方面的工作可见 https://www.techneon.com/ 。

那么，如何证明呢？让我们从费马小定理开始。

如果 p 是一个素数，那么 a ^ (p-1) 对 p 取模就必定为 1 。（此处 a 不为 p 的倍数）

当 p 大于 2 时， p - 1 一定是一个偶数。所以，a ^ (p-1) 一定是一个完全平方数（有整数平方根）。假设它的平方根是 x 。那么， x * x 对 p 取模为 1 ，等价于 x * x - 1 可以被 p 整除。也可以写成 (x+1) (x -1) 可以被 p 整除。

如果 p 是素数，那么，p 就一定可以整除 x+1 或 x -1 两者其一。这就是欧几里得引理。证明很简单，这里就不展开了。注意：当 p 不是素数时，上面的结论是不成立的。比如当 p 等于 15 ，x 等于 4 的时候，p 可以整除 (x+1)(x-1) ，但即不可以整除 x+1 也不可以整除 x-1 。

这样，我们就可以推导出，x 对 p 取模，要么为 1 要么为 -1 (p-1) 。

当 p 是素数时，我们不断的对 a ^ (p-1) 取平方根后，对 p 取模，我们总会得到 1 或 -1 。如果我们得到 -1 , 那么前面的形式二就是成立的；反之，如果我们得到的不是 -1 ，那只能是 1 。这个迭代过程一直得到 1 的话，会一直把 2 这个因子完全除去，最终会满足形式一。

这个原理的逆反就是说，如果 p 是一个合数，以下两个形式必须全部成立：

1. a ^ d 对 p 取模不等于 1 。
2. a ^ (2^r * d) 对 p 取模不等于 -1 。（r 大于等于 0 且小于 s ）

这就是 米勒拉宾素数检验 了。