文档文库

手机版

投诉建议

首页 > 梅森数的概念

梅森数的概念

发布时间：2018-11-14 21:36:10 来源：文档文库

小中大

字号：

手机查看

梅森数的概念

素数也叫质数，是只能被自己和1整除的数，如2、3、5、7、11等。2300年前，古希腊数学家欧几里得证明了素数是无限的，并提出少量素数可写成“2p-1”的形式，这里的指数p也是一个素数。由于这种素数具有许多独特的性质和无穷的魅力，千百年来一直吸引着众多的数学家和无数的数学爱好者对它进行研究和探寻。17世纪法国著名数学家、法兰西科学院奠基人马林·梅森是其中成果较为卓著的一位，因此后人将“2p-1”型的素数称为梅森素数。迄今为止，人类仅发现46个梅森素数。梅森素数珍奇而迷人，因此被人们称为“数海明珠”。

Mersenne number

　　形如2^p－1的正整数，其中p是素数，常记为Mp 。若Mp是素数，则称为梅森素数。p＝2，3，5，7时，Mp都是素数，但M11＝2047＝23×89不是素数。已发现的最大梅森素数是p＝43,112,609的情形，此时 Mp 是一个12,978,189位数。是否有无穷多个梅森素数是数论中未解决的难题之一。

　　也许会有人感到奇怪：素数不就是在大于1的整数中只能被1和其自身整除的数吗？在数学和计算机科学高度发达的今天，为什么发现一个已知的最大素数竟如此困难？找到一个已知的最大梅森素数竟成了科学上的大事？是的，魅力无穷的梅森素数具有许多特异的性质和现象，千百年来一直吸引着众多的数学家和数学爱好者对它进行研究；虽然已经揭示了一些规律，但围绕着它仍然有许多未解之谜，等待着人们去探索。

梅森素数的由来

　　马林·梅森（Marin Mersenne,1588–1648）是17世纪法国著名的数学家和修道士，也是当时欧洲科学界一位独特的中心人物。他与大科学家伽利略、笛卡尔、费马、帕斯卡、罗伯瓦、迈多治等是密友。虽然梅森致力于宗教，但他却是科学的热心拥护者，在教会中为了保卫科学事业做了很多工作。他捍卫笛卡儿的哲学思想，反对来自教会的批评；也翻译过伽里略的一些著作，并捍卫了他的理论；他曾建议用单摆来作为时计以测量物体沿斜面滚下所需时间，从而使惠更斯发明了钟摆式时钟。

　　梅森对科学所作的主要贡献是他起了一个极不平常的思想通道作用。17世纪时，科学刊物和国际会议等还远远没有出现，甚至连科学研究机构都没有创立，交往广泛、热情诚挚和德高望众的梅森就成了欧洲科学家之间的联系的桥梁。许多科学家都乐于将成果寄给他，然后再由他转告给更多的人。因此，他被人们誉为“有定期学术刊物之前的科学信息交换站”。梅森和巴黎数学家笛卡儿、费马、罗伯瓦、迈多治等曾每周一次在梅森住所聚会，轮流讨论数学、物理等问题，这种民间学术组织被誉为“梅森学院”，它就是法兰西科学院的前身。

　　1640年6月，费马在给梅森的一封信中写道：“在艰深的数论研究中，我发现了三个非常重要的性质。我相信它们将成为今后解决素数问题的基础”。这封信讨论了形如2P－1的数（其中p为素数）。早在公元前300多年，古希腊数学家欧几里得就开创了研究2P－1的先河，他在名著《几何原本》第九章中论述完美数时指出：如果2P－1是素数，则2P－1（2P－1）是完美数。

　　梅森在欧几里得、费马等人的有关研究的基础上对2P－1作了大量的计算、验证工作，并于1644年在他的《物理数学随感》一书中断言：对于p=2，3，5，7，13，17，19，31，67，127，257时，2P－1是素数；而对于其他所有小于257的数时，2P－1是合数。前面的7个数（即2，3，5，7，13，17和19）属于被证实的部分，是他整理前人的工作得到的；而后面的4个数（即31，67，127和257）属于被猜测的部分。不过，人们对其断言仍深信不疑，连大数学家莱布尼兹和哥德巴赫都认为它是对的。

　　虽然梅森的断言中包含着若干错误（后文详述），但他的工作极大地激发了人们研究2P－1型素数的热情，使其摆脱作为“完美数”的附庸的地位。可以说，梅森的工作是素

　　研究的一个转折点和里程碑。由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2P－1型的数，为了纪念他，数学界就把这种数称为“梅森数”；并以Mp记之（其中M为梅森姓名的首字母），即Mp=2P－1。如果梅森数为素数，则称之为“梅森素数”（即2P－1型素数）。

　　梅森素数貌似简单，而研究难度却很大。它不仅需要高深的理论和纯熟的技巧，而且需要进行艰巨的计算。即使属于“猜测”部分中最小的M31=231－1=2147483647，也具有10位数。可以想象，它的证明是十分艰巨的。正如梅森推测：“一个人，使用一般的验证方法，要检验一个15位或20位的数字是否为素数，即使终生的时间也是不够的。”是啊，枯燥、冗长、单调、刻板的运算会耗尽一个人的毕生精力，谁愿让生命的风帆永远在黑暗中颠簸！人们多么想知道梅森猜测的根据和方法啊，然而年迈力衰的他来不及留下记载，四年之后就去世了；人们的希望与梅森的生命一起泯灭在流逝的时光之中。看来，伟人的“猜测”只有等待后来的伟人来解决了。

早期历史

　　很早人们就发现，2^2-1=3是个素数，2^3-1=7也是个素数，2^5-1=31，2^7-1=127也都是素数。大家很自然的推测，对所有的素数n，2n-1 是素数。这对不对呢？只要再多试一个，就发现211-1=2047已经不是素数了。实际上，2047=23×89，这是Hudalricus Regius在1536年发现的。

　　对于素数n，判断2n-1 是不是素数并不是很容易的，可以看看以下历史上的事情。1603年，Pietro Cataldi正确地证明了217-1和219-1都是素数。他还给出了对于n=23,29,31,37时2n-1 是素数的证明，但是都是不对的。到了1640年,Fermat证明，Cataldi关于n=23,37的证明是错的，这已经是近40年后的事情了；再过约1一个世纪，1738年，Euler指出了Cataldi关于n=29的证明的错误，而在稍后一点，Euler证明了n=31时Cataldi的结论是正确的。

　　在这个问题上，Marin Mersenne（梅森）做出了很多工作。1644年，他给出一个猜测：不超过257的，能使得2n-1 是素数的全部正整数n只有9个，它们是n=2，3，5，7，13，19，31，127，257是。正是由于他的贡献，这类素数以他命名，当然n可以超过257。

　　定义对于正整数n，称2n-1形状的数为梅森数，记作Mn。如果2n-1 是素数，称这个素数为梅森素数（Mersenne Prime)。

　　但是，Mersenne没有给出证明。直到1750年，才由Euler证明了231-1=7是素数。又过一个世纪，1876年，Lucas证明了2127-1是素数。七年以后，Pervouchine证明了261-1是素数，而且这是Mersenne遗漏的一个。20世纪初，Powers2给出了Mersenne遗漏的另外两个素数289-1和2107。这样，到1947年，n不超过258的全部梅森素数终于确定，是

　　n=2,3,5,7,13,17,31,61,89,107,127,257

探索历程

　　梅森素数就像数学海洋中的一颗璀璨明珠，吸引着一代又一代的研究者去探寻。自梅森提出其断言后，人们发现的已知最大素数几乎都是梅森素数；因此，寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。而梅森断言为素数而未被证实的几个Mp当然首先成为人们研究的对象。

　　1772年，瑞士数学家欧拉在双目失明的情况下，靠心算证明了M31是一个素数，它共有10位数，堪称当时世界上已知的最大素数。欧拉的毅力与技巧都令人赞叹不已，他因此获得了“数学英雄”的美誉。这是寻找已知最大素数的先声。欧拉还证明了欧几里得关于完美数的定理的逆定理，即：每个偶完美数都具有形式2P－1（2P－1），其中2P－1是素数。这就使得偶完美数完全成了梅森素数的“副产品”了。欧拉的艰辛给人们提示：在伟人难以突破的困惑面前要想确定更大的梅森素数，只有另辟蹊径了。

　　100年后，法国数学家鲁卡斯提出了一个用来判别Mp是否是素数的重要定理——鲁卡斯定理。鲁卡斯的工作为梅森素数的研究提供了有力的工具。1883年，数学家波佛辛利用鲁卡斯定理证明了M61也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数：M89和M107，它们分别在1911年与1914年被数学家鲍尔斯发现。

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

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

“手算笔录时代”，人们历尽艰辛，仅找到12个梅森素数。而计算机的产生使寻找梅森素数的研究者如虎添翼。1952年，数学家鲁滨逊等人将鲁卡斯-雷默方法编译成计算机程序，使用SWAC型计算机在短短几小时之内，就找到了5个梅森素数：M521、M607、M1279、M2203和M2281。其后，M3217在1957年被黎塞尔证明是素数；M4253和M4423在1961年被赫维兹证明是素数。1963年，美国数学家吉里斯证明M9689和M9941是素数。1963年9月6日晚上8点，当第23个梅森素数M11213通过大型计算机被找到时，美国广播公司（ABC）中断了正常的节目播放，以第一时间发布了这一重要消息；发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲，为让全世界都分享这一成果，以致于把所有从系里发出的信件都敲上了“211213－1是个素数”的邮戳。

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

2008年8月23日，加州大学洛杉矶分校的电脑发现第四十五已知梅森素数， 2^43,112,609-1 ，一个庞大的12,978,189 位数字！这个素数获得资格，由EFF的十万美元奖金发现第一个千万位数的素数。祝贺埃德森史密斯，负责安装和维护该GIMPS软件在加州大学洛杉矶分校数学系的计算机。仅仅相隔两个星期，2008年9月6日，第46个梅森素数， 2^37,156,667-1 ， 11,185,272 位数，由Hans-Michael Elvenich发现，在Langenfeld，德国科隆附近！这是自 Colquitt 和Welsh在1988年发现2^110,503-1以来首次梅森素数不按顺序被发现。

随着素数P值的增大，每一个梅森素数MP的产生都艰辛无比；而各国科学家及业余研究者们仍乐此不疲，激烈竞争。1979年2月23日，当美国克雷研究公司的计算机专家史洛温斯基和纳尔逊宣布他们找到第26个梅森素数M23209时，人们告诉他们：在两个星期前高中生兰登·诺尔就已得到这一结果。为此，史洛温斯基潜心发愤，花了一个半月的时间，使用CRAY-1型计算机找到了新的梅森素数M44497。这个记录成了当时不少美国报纸的头版新闻。之后，这位计算机专家乘胜前进，使用经过改进的CRAY-XMP型计算机在1983年至1996年间找到了4个梅森素数：M86243、M132049和M216091，他被人们称为“素数大王”。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。而到了1988年，科尔魁特和韦尔什使用NEC-FX2型超高速并行计算机果然捕捉到了一条“漏网之鱼”——M110503。沉寂4年之后，1992年3月25日，英国原子能技术权威机构——哈威尔实验室的一个研究小组宣布他们找到了新的梅森素数M756839。1994年1月14日，史洛温斯基和盖奇为其公司再次夺回发现“已知最大素数”的桂冠——这一素数是M859433。而下一个梅森素数M1257787仍是他们的成果。这一素数是使用CRAY-794超级计算机在1996年取得的。史洛温斯基由于发现7个梅森素数，而被人们誉为“素数大王”。

网格技术的助力

使用超级计算机寻找梅森素数的游戏实在太昂贵了。网格(Grid)这一崭新技术的出现使梅森素数的探寻如虎添翼。1996年初，美国数学家和程序设计师乔治· 沃特曼编制了一个梅森素数计算程序，并把它放在网页上供数学家和数学爱好者免费使用，这就是著名的GIMPS项目。该项目采取网格计算方式，利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。1997年美国数学家及程序设计师斯科特·库尔沃斯基和其他人建立了”素数网”（PrimeNet），使分配搜索区间和向GIMPS发送报告自动化。现在只要人们去GIMPS的主页下载那个免费程序，就可以立即参加GIMPS项目去搜寻梅森素数。

　　12年来，人们通过GIMPS项目找到了12个梅森素数，其发现者来自美国、英国、法国、德国和加拿大。目前，世界上有160多个国家和地区近16万人参加了这一项目，并动用了30万多台计算机联网来进行大规模的分布式计算，以寻找新的梅森素数。该项目的计算能力已超过当今世界上任何一台最先进的超级矢量计算机的计算能力，运算速度超过每秒350万亿次。为了激励人们寻找梅森素数，设在美国的电子新领域基金会(EFF)不久前向全世界宣布了为通过GIMPS项目来探寻梅森素数而设立的奖金。它规定向第一个找到超过1000万位数的个人或机构颁发10万美元。后面的奖金依次为：超过1亿位数，15万美元；超过10亿位数，25万美元。由于史密斯发现的梅森素数已超过1000万位，他将有资格获得EFF颁发的10万美元大奖。其实，绝大多数研究者参与该项目并不是为了金钱，而是出于乐趣、荣誉感和探索精神。

　　时至今日止，人们已经发现了46个梅森素数，并且确定M6972593位于梅森素数序列中的第38位。现把它们列表如下：

由上表可见，梅森素数的分布极不规则。我们甚至可以看到，连找到梅森素数的时间分布都极不规则，有时许多年未能找到一个，而有时则一下找到好几个。探索梅森素数的分布规律似乎比寻找新的梅森素数更为困难。数学家们在长期的摸索中，提出了一些猜想。英国数学家香克斯、美国数学家吉里斯、法国数学家托洛塔和德国数学家伯利哈特就曾分别给出过关于梅森素数分布的猜测，但他们的猜测有一个共同点，就是都以近似表达式给出；而它们与实际情况的接近程度均未尽如人意。

特别值得一提的是，中国数学家及语言学家周海中经过多年的研究，于1992年首先给出了梅森素数分布的精确表达式，从而揭示了梅森素数的重要规律，为人们探寻梅森素数提供了方便；后来这一成果被学术界命名为“周氏猜测”。著名的《科学》杂志上有一篇评论文章指出，这是梅森素数研究中的一项重大突破。

　　不久前，国际电子新领域基金会（IEFF）宣布了由一位匿名者资助的为通过GIMPS项目来寻找新的更大的梅森素数而设立的奖金。它规定向第一个找到超过一千万位数的个人或机构颁发10万美元。后面的奖金依次为：超过1亿位数，15万美元；超过10亿位数，25万美元。但据悉，绝大多数研究者参与该项目不是为了金钱而是出于乐趣、荣誉感和探索精神。可以相信，梅森素数这颗数海明珠正以其独特的魅力，吸引着更多的有志者去寻找和研究。

梅森素数的意义

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

寻找梅森素数在具有十分丰富的理论意义和实用价值。寻找梅森素数是发现已知最大素数的最有效的途径，自欧拉证明M31为当时最大的素数以来，在发现已知最大素数的世界性竞赛中，梅森素数几乎囊括了全部冠军。它的探究推动了数学皇后——数论的研究，促进了计算技术、程序设计技术、密码技术的发展以及快速傅立叶变换的应用。

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

探寻梅森素数最新的意义是：它促进了网格技术的发展。而网格技术将是一项应用非常广阔、前景十分诱人的技术。另外，探寻梅森素数的方法还可用来测试计算机硬件运算是否正确。

　　由于寻找梅森素数需要多种学科的支持，也由于发现新的“最大素数”所引起的国际影响使得对于梅森素数的研究能力已在某种意义上标志着一个国家的科学技术水平，而不仅仅是代表数学的研究水平。英国顶尖科学家马科斯·索托伊甚至认为它是标志科学发展的里程碑。从各国各种传媒（而不仅仅是学术刊物）争相报道新的梅森素数的发现，我们也可清楚地看到这一点。

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

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

　　最后，有必要指出的是：素数有无穷多个，这一点早为欧几里得发现并证得。然而，梅森素数是否有无穷多个？这是目前尚未解决的著名数学难题；而揭开这一未解之谜，正是科学追求的目标。让我们以数学大师希尔伯特的名言来结束本文：“我们必须知道，我们必将知道。”

　　44th Known Mersenne Prime Found!!

　　Lightning strikes twice. On September 4, 2006, in the same room just a few feet away from their last find, Dr. Curtis Cooper and Dr. Steven Boone's CMSU team broke their own world record, discovering the 44th known Mersenne prime, 232,582,657-1. The new prime at 9,808,358 digits is 650,000 digits larger than their previous record prime found last December. However, the new prime falls short of the 10 million digits required for GIMPS to claim the Electronic Frontier Foundation 0,000 award.

　　梅森数(Mersenne numbers)

　　形如Mp=2p－1（其中p为素数）的数被称为梅森数。为使Mp为素数，P为素数是必要条件，但不是充分条件。如果Mp为素数，则称之为梅森素数。1644年，梅森在一本著作（《物理一数学探索》）的序言中提出，当P＝2，3，5，7，13，17，19，31，67，127，257时，2p－1是素数，对于257以内的其他素数p，2p－1都不是素数，但在当时，人们只知道p＝31以前的7个梅森素数的证明（素性证明）。1772年，欧拉才证明M31是素数。M67和M257不是素数，1903年科尔指出

　　M67＝（２）

　　梅森指出的数中，M61， M89， M167也是素数。人们发现，这种数有些很有趣的性质，例如每个形如－1的素数对应一个偶完全数等等，于是人们开始有意识地寻找这种素数，为了纪念提出者把它们命名为梅森素数，一般的－1形数命名为梅森数。

　　直到19世纪上半叶，人们仍然只证明了梅森提出的前8个梅森素数。19世纪后半叶，E．拉库斯提出了一个判断MP是否为素数的方法：若有△＞0使（）＝1且在二次域Q（）中有一个单位数ε适合N(ε)＝－1，则MP为素数的充分必要条件是（mod MP），式中为ε的共扼数。用此法，人们又证明了M61，M89， M107， M127为素数。

　　在电子计算机投入应用之前，人们就证明出上述由从M2到M127这12个梅森素数，从上面举的M67的分解式可以看到P值增大时，MP将迅速增大，使判断计算出现困难。1930年，D．H．莱默尔改进了拉库斯的方法，提出如下判别法则：设p为一奇素数，定义序列

　　L0＝4，

　　…… ，

　　Ln+1＝(Ln2－2)2p－1(n≥0)

　　则2p一1是素数的充要条件是Lp-2＝0。电子计算机出现后，人们利用这一准则，使寻找梅森素数的工作又进行下去。实际上寻找大素数的工作就是寻找梅森素数，因为2p－1这一可构造性的数无疑缩小了寻找的范围，现在所知道的大素数多是梅森素数，这也是研究梅森素数的意义之一。关于梅森素数，有下述两个著名猜想：有无穷多个p使为素数；Mp无平方因数。现都未得到证明，后者的一个结果是L．J．沃伦于1967年证明的：若素数q满足q2 | Mp，则2q-1≡1（mod q2）。梅森数在代数编码理论中亦有应用。

　　Table of Known Mersenne Primes

　　## p

　　(exponent) digits

　　in Mp digits

　　in Pp year discoverer notes

　　1 2 1 1 ---- ----

　　2 3 1 2 ---- ----

　　3 5 2 3 ---- ----

　　4 7 3 4 ---- ----

　　5 13 4 8 1456 anonymous

　　6 17 6 10 1588 Cataldi

　　7 19 6 12 1588 Cataldi

　　8 31 10 19 1772 Euler

　　9 61 19 37 1883 Pervushin

　　10 89 27 54 1911 Powers

　　11 107 33 65 1914 Powers note

　　12 127 39 77 1876 Lucas

　　13 521 157 314 1952 Robinson

　　14 607 183 366 1952 Robinson

　　15 1279 386 770 1952 Robinson

　　16 2203 664 1327 1952 Robinson

　　17 2281 687 1373 1952 Robinson

　　18 3217 969 1937 1957 Riesel

　　19 4253 1281 2561 1961 Hurwitz

　　20 4423 1332 2663 1961 Hurwitz

　　21 9689 2917 5834 1963 Gillies

　　22 9941 2993 5985 1963 Gillies

　　23 11213 3376 6751 1963 Gillies

　　24 19937 6002 12003 1971 Tuckerman [Tuckerman71]

　　25 21701 6533 13066 1978 Noll & Nickel [NN80]

　　26 23209 6987 13973 1979 Noll "

　　27 44497 13395 26790 1979 Nelson & Slowinski [Slowinski79]

　　28 86243 25962 51924 1982 Slowinski [Ewing83]

　　29 110503 33265 66530 1988 Colquitt & Welsh [CW91]

　　30 132049 39751 79502 1983 Slowinski

　　31 216091 65050 130100 1985 Slowinski

　　32 756839 227832 455663 1992 Slowinski & Gage et al. (web page)

　　33 859433 258716 517430 1994 Slowinski & Gage

　　34 1257787 378632 757263 1996 Slowinski & Gage (web page)

　　35 1398269 420921 841842 1996 Armengaud, Woltman,

　　et al. (GIMPS) (web page)

　　36 2976221 895932 1791864 1997 Spence, Woltman,

　　et al. (GIMPS) (web page)

　　37 3021377 909526 181**** **** Clarkson, Woltman, Kurowski