也谈素数判断（修订版）

素数，又称质数、Prime Number，就是只能被1和它自己整除的正整数。素数本身的特殊性质决定了其应用的广泛性，比如作为哈希函数的基数或是加密函数共钥的参数。因此，素数的问题也是平时讨论中比较多的。一个比较常见的问题就是，如何判断一个数（假设为N）是否为素数？本文对常用的几种进行比较：

• 采用0到N-1的所有整数去尝试整除N，如果其间有任意的数能被N整除，说明N是合数，否则输出素数。
• 遍历2以上到N的平方根以下的每一个整数，是不是能被N整除
• 遍历2以上到N的平方根以下的每一个整数，是不是能被N整除；如果不能被N整除，同时也就排除了该整数的倍数，将其从待除数队列中删除；如此可将耗费性能的除法运算消耗进一步压缩
• 遍历2以上N的平方根以下的每一个素数，是不是能整除N;(这个方法是上面方法的改进，但要求N平方根以下的素数已全部知道)

方法一是最为朴素的方法，事实上，并不需要遍历小于N的所有整数，其实只要遍历小于sqrt(N)的所有整数即可，这就是方法二。为什么这样说呢？这里我们可以用反证法加以证明，假设我们采用前述方法进行遍历，直到遇到某个k>sqrt(N)，才能被N整除，这样，必然存在一个整数l=N/k，l<sqrt(N)，l同时也能被N整除，而在这种情况下，l肯定在k之前就被测试过了，这样就与前面的假设相矛盾了。

与欧几里得同时代的数学家埃拉托色尼首先给出了求素数的方法，现在人们称之为“埃拉托尼筛子”。他求素数的方法如下。首先从2开始，写出自然数：2，3，4，5，6，7，8，9 … 100，然后，把其中的一切合数划去，划掉合数的原则是，在这一列数中，第一个数２满足素数的定义，把它保留下来。随后把能被2的倍数都划去，因为它们都是合数。接着在数2后的没有被划去的第一个数是3，因为它只被1和它本身整除，所以它是一个合数，把它也划去。剩下没有被划去的第一个有选举权是5，它只能被这和它本身整除，所以它也是一个素数。如此连续不断地划下去，最后剩下的数都是素数。为什么把这种方法叫做“厄拉多塞筛子”呢？因为厄拉多塞在求素数时，把自然数写在一块白蜡的木板上，并逐个在写着合数的位置上刺一个孔，这样白蜡板上被刺了很多的小孔，好像一个筛子。把所有的合数“筛掉”剩下的就都是素数。用“埃拉托尼筛子”可得到100以内的25个素数：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97。这里得到的启示是，我们不需要像前面那样，“遍历2以上到N的平方根以下的每一个整数，是不是能被N整除”，从中得到的启示，引出了方法三。

我们使用“埃拉托尼筛子”方法在黑板上筛选数字的时候，发现，方法三中去除的都是合数，即留下的都是素数，因此实际与待比对数进行整除操作的都是素数；如果我们事先知道某段区间的素数（事实上，<2000将会使个不错的范围），则可以将方法三进一步优化为方法四，减少了大量除法操作的开销。

上述四种方法看似可以满足日常的需求，但对于实际中的大素数判断还是无能为力，例如：N=2^127-1是一个38位数，要验证它是否为素数，用上面几个不同的方法，假设计算机能每秒钟计算１亿次除法，那么方法三要用4136年，方法四要用93年……接下来将会介绍一种只需要1秒钟的方法——Rabin-Miller算法。首先来看一下费马小定理：

我们可以来验证一下费马小定理，已知67是一个素数，而2^66mod 67=1。上述定理的逆命题又被称为中国猜测（中国数学家早于费马2000年提出），其描述为：2^(p-1)除以p的余数为1，可得出p是素数。很遗憾，该论断是错误的，比如p=341符合上述条件，却不是一个素数。因此我们修改中国猜测为如下推论：

可见，中国猜测只是素数判定的一个必要条件。有些合数也满
足费马小定理的条件。这些和数被称做卡米切尔数数，除341外，其余的卡米切尔数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中，大约只有255个卡米切尔数。

至于如何从费马小定理推导出Rabin-Miller算法，wiki上有很好的证明过程：
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

该算法的过程如下：

• 首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
• 选择一个小于p的随机数a。
• 设j=0且z=a^m mod p
• 如果z=1或z=p-1，那麽p通过测试，可能使素数
• 如果j>0且z=1, 那麽p不是素数
• 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
• 如果j=b 且z<>p-1，不是素数

这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。

我们举一个例子来说明：

假设我们想知道n = 221是否为一个素数，首先我们将n − 1 = 220写成2^2*55，即s = 2以及 d = 55。我们随机选择一个a < n，比如说a = 174。接着进行如下计算：
a^2^0*d mod n = 174^55 mod 221 = 47 ≠ 1, n − 1
a^2^1*d mod n = 174^110 mod 221 = 220 = n − 1

由于此时220 ≡ −1 mod n，所以我们说221很有可能是一个素数，或者它（174）是一个很强的“伪素数”。我们打算再试一次，这一次取a = 137：
a^2^0·d mod n = 137^55 mod 221 = 188 ≠ 1, n − 1
a^2^1·d mod n = 137^110 mod 221 = 205 ≠ n − 1

这次137成了证明221是合数的见证人，尽管看起来很像一个素数，221其实是一个合数，因为221 = 13 * 17:)

学到了数学知识，重要的是思维方式