找回密码
 新注册用户
搜索
查看: 7261|回复: 3

[分享] 梅森素数为何那样火爆?

[复制链接]
发表于 2012-10-16 16:03:01 | 显示全部楼层 |阅读模式
一个国际民间组织悬赏 10万美元找最大梅森数;这导致了180多个国家20多万人参加了“因特网梅森素数大搜索”(GIMPS)国际合作,动用了40多万台计算机联网来进行“搜捕”。什么是梅森素数?梅森素数为何那样火爆?

梅森素数(Mersenne Prime)是指形如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位数。

2300多年来,人类仅发现47个梅森素数。由于这种素数珍奇而迷人,因此被人们誉为“数海明珠”。自梅森提出其断言后,人们发现的已知最大素数几乎都是梅森素数;因此,寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。
  梅森素数的研究难度极大,它不仅需要高深的理论和纯熟的技巧,而且需要进行艰苦的计算。
  1772年,瑞士数学家欧拉在双目失明的情况下,靠心算证明了M31是一个素数,它共有10位数,堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完美数的定理的逆定理,即:每个偶完美数都具有形式(2^p-1)2^(p-1),其中2^p-1是素数。
  100年后,法国数学家鲁卡斯提出了一个用来判别Mp是否是素数的重要定理——鲁卡斯定理。鲁卡斯的工作为梅森素数的研究提供了有力的工具。
  1883年,数学家波佛辛利用鲁卡斯定理证明了M61也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数:M89和M107,它们分别在1911年与1914年被数学家鲍尔斯发现。
  1903年,数学家柯尔第一个否定了“M67为素数”这一自梅森断言以来一直被人们相信的结论。算出2^67-1,等于193707721×761838257287。
  1922年,数学家克莱契克进一步验证了M257并不是素数,而是合数。
  1930年,美国数学家雷默改进了鲁卡斯的工作,给出了一个针对Mp的新的素性测试方法,即鲁卡斯-雷默方法:Mp>3是素数的充分必要条件是Lp-2=0,其中L0=4,Ln+1=(Ln-2)ModMp。这一方法直到今天的“计算机时代”仍发挥重要作用。
  1952年,数学家鲁滨逊等人将鲁卡斯-雷默方法编译成计算机程序,使用SWAC型计算机在几个月内,就找到了5个梅森素数:M521、M607、M1279、M2203和M2281。
  1957年 ,数学家黎塞尔证明M3217是素数;
  1961年,数学家赫维兹证明M4253和M4423是素数。
  1963年,美国数学家吉里斯证明M9689和M9941是素数。
  1963年9月6日晚上8点,第23个梅森素数M11213通过大型计算机被找到。发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲,以致于把所有从系里发出的信件都敲上了“2^11213-1是个素数”的邮戳。
  1971年3月4日晚,塔可曼使用IBM360-91型计算机找到新的梅森素数M19937。而到1978年10月,世界几乎所有的大新闻机构(包括中国的新华社)都报道了以下消息:两名年仅18岁的美国高中生诺尔和尼科尔使用CYBER174型计算机找到了第25个梅森素数:M21701。
  1979年2月,诺尔找到第26个梅森素数M23209。
  1979年4月,史洛温斯基使用CRAY-1型计算机找到梅森素数M44497。使用经过改进的CRAY-XMP型计算机在1983年至1985年间找到了3个梅森素数:M86243、M132049和M216091。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。
  1988年,科尔魁特和韦尔什使用NEC-FX2型超高速并行计算机发现M110503。
  1992年3月25日,哈威尔实验室(英国原子能技术权威机构)的一个研究小组宣布他们找到梅森素数M756839。
  1994年1月14日,史洛温斯基和盖奇再次夺回发现已知最大素数的桂冠——这一素数是M859433。而下一个梅森素数M1257787仍是他们的成果。(这一素数是使用CRAY-794超级计算机在1996年取得的。史洛温斯基由于发现7个梅森素数,而被人们誉为“素数大王”。)
  2008年8月,美国加州大学洛杉矶分校(UCLA)的计算机专家史密斯(E.Smith)通过参加了一个名为“因特网梅森素数大搜索”(GIMPS)的国际合作项目,发现了第46个也是最大的梅森素数2^43112609-1,该素数也就是2自身相乘43112609次减1,它有12978189位数,如果用普通字号将这个巨数连续写下来,它的长度可超过50公里!最近,这一成就被美国的《时代》杂志评为“2008年度50项最佳发明”之一,排名在第29位。

梅森素数的分布极不规则。找到梅森素数的时间分布都极不规则,有时许多年未能找到一个,而有时则一下找到好几个。探索梅森素数的分布规律似乎比寻找新的梅森素数更为困难。数学家们在长期的摸索中,提出了一些猜想。英国数学家香克斯、美国数学家吉里斯、法国数学家托洛塔和德国数学家伯利哈特曾分别给出过关于梅森素数分布的猜测,但他们的猜测有一个共同点,就是都以近似表达式给出;而它们与实际情况的接近程度均未尽如人意 。
  中国数学家和语言学家周海中是这方面研究的领先者——他运用联系观察法和不完全归纳法,于1992年2月首次给出了梅森素数分布的精确表达式,为人们寻找这一素数提供了方便;后来这一重要成果被国际上命名为“周氏猜测”。著名的《科学》杂志上有一篇评论文章指出,这是梅森素数研究中的一项重大突破。美籍挪威数论大师、菲尔茨奖和沃尔夫奖得主阿特勒·塞尔伯格认为:周氏猜测具有创新性,开创了富于启发性的新方法;其创新性还表现在揭示新的规律上。

1996年初,美国数学家和程序设计师乔治· 沃特曼编制了一个梅森素数计算程序,并把它放在网页上供数学家和数学爱好者免费使用,这就是著名的“因特网梅森素数大搜索”(GIMPS)项目。该项目采取网格计算方式,利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。1997年美国数学家及程序设计师斯科特·库尔沃斯基和其他人建立了”素数网”(PrimeNet),使分配搜索区间和向GIMPS发送报告自动化。现在只要人们去GIMPS的主页下载那个免费程序,就可以立即参加该项目来搜寻新的梅森素数。
  为了激励人们寻找梅森素数和促进网格技术发展,设在美国的电子新领域基金会(EFF)于1999年3月向全世界宣布了为通过GIMPS项目来寻找新的更大的梅森素数而设立的奖金。它规定向第一个找到超过1000万位数的个人或机构颁发10万美元。后面的奖金依次为:超过1亿位数,15万美元;超过10亿位数,25万美元。其实,绝大多数研究者参与该项目并不是为了金钱,而是出于乐趣、荣誉感和探索精神。
  截止2012年7月,人们通过GIMPS项目找到了13个梅森素数,其发现者来自美国、英国、法国、德国、加拿大和挪威。世界上有180多个国家和地区超过23万人参加了这一国际合作项目,并动用了45万多台计算机联网来寻找新的梅森素数。该项目的计算能力已超过当今世界上任何一台最先进的超级矢量计算机的计算能力,运算速度达到每秒700万亿次。著名的《自然》杂志说:GIMPS项目不仅会进一步激发人们对梅森素数寻找的热情,而且会引起人们对网格技术应用研究的高度重视。

梅森素数历来都是数论研究的一项重要内容,也是当今科学探索的热点和难点之一。自古希腊时代直至17世纪,人们寻找梅森素数的意义似乎只是为了寻找完美数。但自梅森提出其著名断言以来,特别是欧拉证明了欧几里得关于完美数的定理的逆定理以来,完美数已仅仅是梅森素数的一种“副产品”了。
  寻找梅森素数在现代已有了十分丰富的意义。寻找梅森素数是发现已知最大素数的最有效的途径,自欧拉证明M31为当时最大的素数以来,在发现已知最大素数的世界性竞赛中,梅森素数几乎囊括了全部冠军。
  寻找梅森素数是测试计算机运算速度及其他功能的有力手段。如M1257787就是1996年9月美国克雷公司在测试其最新超级计算机的运算速度时得到的。梅森素数在推动计算机功能改进方面发挥了独特作用。发现梅森素数不仅仅需要高功能的计算机,它还需要素数判别和数值计算的理论与方法以及高超巧妙的程序设计技术等等,因而它还推动了数学皇后——数论的发展,促进了计算数学、程序设计技术的发展。
  由于寻找梅森素数需要多种学科的支持,也由于发现新的“大素数”所引起的国际影响使得对于梅森素数的研究能力已在某种意义上标志着一个国家的科学技术水平,而不仅仅是代表数学的研究水平。
  梅森素数在实用领域也有用武之地。现在人们已将大素数用于现代密码设计领域。其原理是:将一个很大的数分解成若干素数的乘积非常困难,但将几个素数相乘却相对容易得多。在这种密码设计中,需要使用较大的素数,素数越大,密码被破译的可能性就越小。
  寻找梅森素数最新的意义是:它促进了分布式计算技术的发展。从最新的13个梅森素数是在因特网项目中发现这一事实,可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能;这是一个前景非常广阔的领域。它的探究还推动了快速傅立叶变换的应用。
  在当代梅森素数的探究需要多种学科和技术的支持,所以许多科学家认为:它的研究成果,一定程度上反映了一国的科技水平。英国顶尖科学家、牛津大学教授马科斯·索托伊甚至认为它是人类智力发展在数学上的一种标志,也是科学发展的里程碑之一。
  可以相信,梅森素数这颗数学海洋中的璀璨明珠正以其独特的魅力,吸引着更多的有志者去寻找和研究。 最后,有必要指出的是:素数有无穷多个,这一点早为欧几里得发现并证得。然而,梅森素数是否有无穷多个?这是尚未解决的著名数学难题;而揭开这一未解之谜,正是科学追求的目标。
回复

使用道具 举报

发表于 2013-5-31 11:44:21 | 显示全部楼层
严重学习!
回复

使用道具 举报

发表于 2013-5-31 12:24:25 | 显示全部楼层
其实就是闲的
回复

使用道具 举报

发表于 2013-6-1 16:06:35 | 显示全部楼层
本帖最后由 mhsk 于 2013-6-1 16:08 编辑

楼上高人!一句话说中要害了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-28 21:12

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表