米勒拉宾素数检验
今年 1024 程序员节公司搞活动，让我做一次分享。我在分享会上谈及程序优化时，说道优化算法减少时间复杂度的优化往往比优化代码本身更优化。举的一个例子就是检测一个整数是否是素数的问题。
米勒拉宾素数检验法比普通方法有数量级上的性能提高。当时我说道，这个算法的原理其实并不复杂，其证明过程有高中数学知识就可以理解，并不需要多深奥的数学知识。
会后，有同学提出了疑问。他怀疑一个高中生真的能看懂 wikipedia 上的解释 。仔细读了一遍后，我认为，对于中学生来说，难懂的可能只是其中的一些专有术语罢了，那些中学数学课本上没有引入。其内核还是挺好懂的。而且，这篇中文版写的（以及排版）不太好，远没有英文版清晰 。或许只要看英文版就立刻明白了。
我也许可以写一篇没那么多术语，但也不够严谨的解释。
说道素数检验法，最基本的方法就是按素数的定义，拿这个整数去除比它小的所有大于 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 ， 以下两个形式之一必然成立：
- a ^ d 对 p 取模为 1 。
- 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 是一个合数，以下两个形式必须全部成立：
- a ^ d 对 p 取模不等于 1 。
- a ^ (2^r * d) 对 p 取模不等于 -1 。（r 大于等于 0 且小于 s ）
这就是 米勒拉宾素数检验 了。