梅森素数的探索之旅

2009年5月22日，对于很多人来说并不是什么特别的日志，不过数学界这边又传来了一个“喜讯”：我们已经找到了第47个梅森素数，即$2^{42643801}-1$是一个素数！新的素数已于6月12日通过法国的Tony Reix的验证，这是目前的第二大素数，有12,837,064位数字！这是通过参加一个名为“因特网梅森素数大搜索”(GIMPS)的国际合作项目而发现的。让我们来共同回顾这一素数之旅！

素数/梅森素数

素数，现在课本上都已经成为“质数”了，不过目前很多数学家、爱好者都还是将其称为素数（也许这个名字好听）。这是指一些不可分解成两个比它本身小的两个整数相乘的形式的数，如2、3、5、7等。除了2外，所有的素数都是奇数。

2000年前，古希腊的毕达哥拉斯学派提出了一种有趣的数字：这个数的所有因子（不包含这个数本身）之和等于原数，这种数字被称为“完全数”，如6=1+2+3，1、2、3是6的所有因子。从此，这种数字就被作为一个有趣的课题流传了下来。

大数学家欧几里得提出了一个构造完全数的式子：$2^{p-1}(2^p-1)$，其中$2^p-1$是一个素数。也许欧几里得并不会想到，这个式子带来了一个人们经久不衰的话题，那就是寻找诸如$2^p-1$的梅森素数。当然，第一次把这种形式的素数独立出来研究的，是数学家梅森而不是欧几里得。现在，我们找到了一个梅森素树，就等价于找到了一个完全数。因为，目前没有发现任何奇数形式的完全数，偶数形式的也只有这一种。

寻找历程

然而，寻找梅森素树的历程并不平坦，人们很早就发现，形如$2^p-1$的素数，p一定也是素数。因为，如果p为合数，可以写成p=ab，那么$2^{ab}-1=(2^a)^b-1=(2^b)^a-1$，必定含有因数$2^a-1$和$2^b-1$。

但是，这个定理的逆定理不成立，即p为素数$2^p-1$未必是素数。如$2^{11}-1=23\cdot 89$。更糟糕的是，这种素数在自然数中少得可怜。直到1500年，才发现了p=2,3,5,7,13这五个梅森素数。

此后著名数学家如费马、笛卡尔、莱布尼兹、欧拉、哥德巴赫、鲁卡斯、香吉斯、柯尔、吉里斯等都曾对这种质数进行过研究，马丁·梅森是其中成果较为卓著的一位，因此后人将“$2^p-1$”形式的质数称为梅森素数。

证明/判断

卢卡斯-莱默检验法是现在已知的检测梅森数素性的最好的方法。
该方法由爱德华·卢卡斯于1878年发现，并由莱默1930年代作了改进，因此得名。

该方法基于循环数列的计算，其原理是：
$M_p$为素数当且仅当$M_P$整除$S_{n-2}(S_0=4,S_k = S_{k-1}^2-2,k > 0)$。

假设我们想验证M3 = 7是素数。我们从s=4开始，并更新3-2 = 1次，把所有的得数模7：
s ← ((4 × 4) - 2) mod 7 = 0
由于我们最终得到了一个能被7整除的s，因此M3是素数。

另一方面，M11 = 2047 = 23 × 89就不是素数。我们仍然从s=4开始，并更新11-2 = 9次，把所有的得数模2047：
s ← ((4 × 4) - 2) mod 2047 = 14
s ← ((14 × 14) - 2) mod 2047 = 194
s ← ((194 × 194) - 2) mod 2047 = 788
s ← ((788 × 788) - 2) mod 2047 = 701
s ← ((701 × 701) - 2) mod 2047 = 119
s ← ((119 × 119) - 2) mod 2047 = 1877
s ← ((1877 × 1877) - 2) mod 2047 = 240
s ← ((240 × 240) - 2) mod 2047 = 282
s ← ((282 × 282) - 2) mod 2047 = 1736

由于s最终仍未能被2047整除，因此M11=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。

对$M_p$（p是素数）有：
若a是$M_p$的因数，则a有如下性质：
a ≡ 1 mod 2p
a ≡ ±1 mod 8

寻找/计算

梅森质数貌似简单，但研究难度却很大。它不仅需要高深的理论和纯熟的技巧，而且还需要进行艰巨的计算。

1995年底～1996年初美国数学家及程序设计师乔治·沃特曼编制了一个梅森质数计算程序，并把它放在网页上供数学家和数学爱好者免费使用，这就是闻名世界的GIMPS项目。该项目采取分布式计算方式，利用大量普通计算机的闲置计算资源来获得相当于超级计算机的运算能力。著名的英国《自然》杂志曾有一则报道认为：GIMPS项目不仅会进一步激发人们对梅森质数探寻的热情，而且会引起人们对分布式计算应用研究的高度重视。1997年美国数学家及程序设计师斯科特·库尔沃斯基和其他人建立了“素数网”(PrimeNet)，使分配搜索区间和向GIMPS发送报告自动化。现在只要人们去GIMPS的主页下载一个名为Prime95免费程序，就可以立即参加GIMPS项目来搜寻梅森质数。

www.mersenne.org - GIMPS官方网站
www.mersenneforum.org - GIMPS官方论坛

参考：
http://songshuhui.net/archives/12950.html

http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0#.E6.A2.85.E6.A3.AE.E6.95.B0.E7.9A.84.E7.B4.A0.E6.80.A7.E6.A3.80.E9.AA.8C

转载到请包括本文地址：https://kexue.fm/archives/63

更详细的转载事宜请参考：《科学空间FAQ》