梅森素数

梅森素数，它是发现已知最大素数的有效途径，它推动了数论研究，也促进了计算数学、程序设计技术、网格计算技术以及密码技术的发展，梅森素数探究难度较大，它不仅需要高深的理论和纯熟的技巧，而且还需要进行艰巨的计算。

梅森素数 - 概述

梅森素数，(Mersenne Primes)，17世纪法国数学家、法兰西科学院奠基人马林•梅森，梅森素数指形如2^p－1的正整数，其中指数p是素数，常记为Mp 。若Mp是素数，则称为梅森素数。p=2，3，5，7时，Mp都是素数，但M11=2047=23×89不是素数 ，是否有无穷多个梅森素数是数论中未解决的难题之一。截止2012年7月累计发现47个梅森素数，最大的是p=43,112,609，此时 Mp 是一个12,978,189位数。
这种素数历来是数论研究的一项重要内容，也是当今科学探索的热点和难点之一，由于梅森素数珍奇而迷人，它被人们誉为“数论中的钻石”。

梅森素数 - 历史发现

早在公元前300多年，古希腊数学家欧几里得就开创了研究2^P－1的先河，他在名着《几何原本》第九章中论述完美数时指出：如果2^P－1是素数，则2^P－1（2^P－1）是完美数。

1640年6月，费马在给梅森的一封信中写道：“在艰深的数论研究中，我发现了三个非常重要的性质。我相信它们将成为今后解决素数问题的基础”，这封信讨论了形如2^P－1的数（其中p为素数）。梅森在欧几里得、费马等人的有关研究的基础上对2^P－1作了大量的计算、验证工作。

1644年，在他的《物理数学随感》一书中断言：对于p=2，3，5，7，13，17，19，31，67，127，257时，2^P－1是素数；而对于其他所有小于257的数时，2^P－1是合数。前面的7个数（即2，3，5，7，13，17和19）属于被证实的部分，是他整理前人的工作得到的；而后面的4个数（即31，67，127和257）属于被猜测的部分。

1772年，瑞士数学家欧拉在双目失明的情况下，靠心算证明了M31是一个素数，它共有10位数，堪称当时世界上已知的最大素数，他因此获得了“数学英雄”的美誉。这是寻找已知最大素数的先声。欧拉还证明了欧几里得关于完美数的定理的逆定理，即：每个偶完美数都具有形式2^P－1（2^P－1），其中2^P－1是素数。这就使得偶完美数完全成了梅森素数的“副产品”了。

1883年，数学家波佛辛利用鲁卡斯定理证明了M61也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数：M89和M107，它们分别在1911年与1914年被数学家鲍尔斯发现。

1903年，在美国数学学会的大会上，数学家柯尔作了一个一言不发的报告，他在黑板上先算出2^67－1，接着又算出193707721×761838257287，两个结果相同，这在美国数学学会开会的历史上是绝无仅有的一次。他第一个否定了“M67为素数”这一自梅森断言以来一直被人们相信的结论。1922年，数学家克莱契克进一步验证了M257并不是素数，而是合数（但他没有给出这一合数的因子，直到20世纪80年代人们才知道它有3个素因子）。

1930年，美国数学家雷默改进了鲁卡斯的工作，给出了一个针对Mp的新的素性测试方法，即鲁卡斯-雷默方法：Mp＞3是素数的充分必要条件是Lp-2=0，其中L0=4，Ln+1=(Ln－2)ModMp。这一方法直到今天的“计算机时代”仍发挥重要作用。

1952年，数学家鲁滨逊等人将鲁卡斯-雷默方法编译成计算机程序，使用SWAC型计算机在短短几小时之内，就找到了5个梅森素数：M521、M607、M1279、M2203和M2281。其后，M3217在1957年被黎塞尔证明是素数；M4253和M4423在1961年被赫维兹证明是素数。

1963年，美国数学家吉里斯证明M9689和M9941是素数。1963年9月6日晚上8点，当第23个梅森素数M11213通过大型计算机被找到时，美国广播公司（ABC）中断了正常的节目播放，以第一时间发布了这一重要消息；发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲，以致于把所有从系里发出的信件都敲上了“2^11213－1是个素数”的邮戳。

1971年3月4日晚，美国哥伦比亚广播公司（CBS）中断了正常节目播放，发布了塔可曼使用IBM360-91型计算机找到新的梅森素数M19937的消息。而到1978年10月，世界几乎所有的大新闻机构（包括中国的新华社）都报道了以下消息：两名年仅18岁的美国高中生诺尔和尼科尔使用CYBER174型计算机找到了第25个梅森素数：M21701。

1979年2月23日，当美国克雷研究公司的计算机专家史洛温斯基和纳尔逊宣布他们找到第26个梅森素数M23209时，人们告诉他们：在两个星期前诺尔已得到这一结果。为此，史洛温斯基潜心发愤，花了一个半月的时间，使用CRAY-1型计算机找到了新的梅森素数M44497。

1983年至1985年间找到了3个梅森素数：M86243、M132049和M216091。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。

1988年，科尔魁特和韦尔什使用NEC-FX2型超高速并行计算机果然捕捉到了一条“漏网之鱼”——M110503。

1992年3月25日，英国原子能技术权威机构——哈威尔实验室的一个研究小组宣布他们找到了新的梅森素数M756839。

1994年1月14日，史洛温斯基和盖奇为其公司再次夺回发现“已知最大素数”的桂冠——这一素数是M859433。

在1996年，梅森素数M1257787仍是他们的成果，这一素数是使用CRAY-794超级计算机取得的，史洛温斯基由于发现7个梅森素数，而被人们誉为“素数大王”。

2004年5月15日，美国国家海洋和大气局顾问、数学爱好者乔希·芬德利(Josh Findley)用一台装有2.4GHZ奔腾处理器的个人计算机，找到了当时世界上已知最大的梅森素数。该素数为2的24036583次方减1(即2^24036583－1)，它有7235733位数，如果用普通字号将这个数字连续写下来，它的长度可达3万米，它是2000多年来人类发现的第41个梅森素数，也是当时已知的最大素数。

2005年2月28日，一名德国数学爱好者于2月18日发现了一个新的素数，这个素数有7816230位，可以写成2^25964951-1。

2007年秋季，美国加州大学洛杉矶分校(UCLA)的计算机专家埃德森·史密斯利用数学系所有的计算机参加了一个名为“因特网梅森素数大搜索”(GIMPS)的国际合作项目，前不久他在其中的一台计算机上偶然发现了这个超大的素数。这是人类迄今为止发现的第46个也是最大的梅森素数。2^43112609-1，也就是2自身相乘43112609次减1，它有12978189位数，如果用普通字号将这个巨数连续写下来，这个梅森素数的长度可超过50公里。

梅森素数 - 分布规律

周氏猜测是中国数学家及语言学家周海中于1992年在《梅森素数的分布规律》一文中提出的猜测。

其内容为：当2^（2^n）＜p＜2^（2^（n+1））时，Mp有2^（n+1）－1个是素数。

周海中还据此作出了p＜2^（2^（n+1））时梅森素数的个数为2^（n+2）－ n － 2的推论。 （注：n为自然数，p为素数，Mp为梅森数）

梅森素数 - 研究意义

自古希腊时代直至17世纪，人们寻找梅森素数的意义似乎只是为了寻找完美数。但自梅森提出其着名断言以来，特别是欧拉证明了欧几里得关于完美数的定理的逆定理以来，完美数已仅仅是梅森素数的一种“副产品”了。

寻找梅森素数是发现已知最大素数的最有效的途径，自欧拉证明M31为当时最大的素数以来，在发现已知最大素数的世界性竞赛中，梅森素数几乎囊括了全部。

寻找梅森素数是测试计算机运算速度及其他功能的有力手段。如M1257787就是1996年9月美国克雷公司在测试其最新超级计算机的运算速度时得到的。梅森素数在推动计算机功能改进方面发挥了独特作用。发现梅森素数不仅仅需要高功能的计算机，它还需要素数判别和数值计算的理论与方法以及高超巧妙的程序设计技术等等，因而它还推动了数学皇后——数论的发展，促进了计算数学、程序设计技术的发展。

梅森素数在实用领域也有用武之地，现在人们已将大素数用于现代密码设计领域。其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多。在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。

寻找梅森素数促进了分布式计算技术的发展。从最新的7个梅森素数是在因特网项目中发现这一事实，分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能；这是一个前景非常广阔的领域。

梅森素数促进了当代计算技术、密码技术、程序设计技术的发展以及快速傅立叶变换的应用。梅森素数的意义还在于它促进了网格技术的发展；而网格技术是一项应用非常广阔的高新技术。另外，梅森素数还可用来测试计算机硬件运算是否正确。