梅森素数

编辑:传播网互动百科 时间:2019-12-10 01:54:18
编辑 锁定
同义词 梅森尼数一般指梅森素数
梅森素数是由梅森数而来。
所谓梅森数,是指形如2p-1的一类数,其中指数p是素数,常记为Mp 。如果梅森数是素数,就称为梅森素数。
因式分解法可以证明,若2n-1是素数,则指数n也是素数;反之,当n是素数时,2n-1(即Mp)却未必是素数。前几个较小的梅森数大都是素数,然而梅森数越大,梅森素数也就越难出现。
是否存在无穷多个梅森素数是数论中未解决的著名难题之一。目前仅发现49个梅森素数,最大的是 274207281-1(即2的74207281次方减1),有22338618位数。
中文名
梅森素数
外文名
Mersenne prime
别    名
梅森质数
称    号
数海明珠、数论中的钻石、素数王
名称由来
以马林·梅森的名字命名
已发现数量
49个
最新寻找方式
利用网格技术
问题和猜想
梅森素数是否无穷,如何分布
应用领域
计算机科学、密码学
相关课题
完全数

梅森素数概述

编辑
素数是指在大于1的整数中只能被1和其自身整除的数(如2、3、5、7等等)。素数有无穷多个,但目前却只发现有极少量的素数能表示成 2p-1(p为素数)的形式,这就是梅森素数。它是以17世纪法国数学家马林·梅森的名字命名。梅森素数是数论研究中的一项重要内容,自古希腊时代起人们就开始了对梅森素数的探索。由于这种素数具有着独特的性质(比方说和完全数密切相关)和无穷的魅力,千百年来一直吸引着众多数学家(包括欧几里得、费马、欧拉等)和无数的数学爱好者对它进行探究。在现代,梅森素数不但在计算机科学、密码学等领域有重要的应用价值,它还是人类好奇心求知欲荣誉感的最好见证。

梅森素数由来

编辑
马林·梅森(1588-1648) 马林·梅森(1588-1648)
早在公元前300多年,古希腊数学家欧几里得就开创了研究2p-1的先河。他在名著《几何原本》第九章中论述完全数时指出:如果2p-1是素数,则 2p-1(2p-1)是完全数。
1640年6月,费马在给马林·梅森(Marin Mersenne)的一封信中写道:“在艰深的数论研究中,我发现了三个非常重要的性质,我相信它们将成为今后解决素数问题的基础。” 这封信讨论了形如2p-1的数。
马林·梅森是当时欧洲科学界一位独特的中心人物,他与包括费马在内的很多科学家经常保持通信联系,讨论数学、物理等问题。17世纪时,学术刊物和科研机构还没有创立,交往广泛、热情诚挚的梅森就成了欧洲科学家之间联系的桥梁,许多科学家都乐于将成果告诉他,然后再由他转告给更多的人。梅森还是法兰西学院的奠基人,为科学事业做了很多有益的工作,被选为 “100位在世界科学史上有重要地位的科学家” 之一。[1] 
梅森在欧几里得、费马等人有关研究的基础上对2p-1作了大量的计算、验证,并于1644年在他的《物理数学随感》一书中断言:在不大于257的素数中,当p = 2、3、5、7、13、17、19、31、67、127、257 时,2p-1是素数,其它都是合数。前面的7个数(即2、3、5、7、13、17、19)已被前人所证实,而后面的4个数(即31、67、127、257)则是梅森自己的推断。由于梅森在科学界有着崇高的学术地位,人们对其断言都深信不疑。
后来人们才知道梅森的断言其实包含着若干错漏。不过他的工作却极大地激发了人们研究2p-1型素数的热情,使其摆脱作为 “完全数” 的附庸地位,可以说梅森的工作是2p-1型素数研究的一个转折点和里程碑。由于梅森学识渊博、才华横溢、为人热情以及最早系统而深入地研究2p-1型的数,为了纪念他,数学界就把这种数称为 “梅森数”,并以Mp记之(其中M为梅森姓名的首字母),即Mp=2p-1。如果梅森数为素数,则称之为 “梅森素数”(即2p-1型素数)。

梅森素数寻找历程

编辑
2300多年来,人类仅发现49个梅森素数,由于这种素数珍奇而迷人,因此被人们誉为 “数海明珠” 。自梅森提出其断言后,人们发现的已知最大素数几乎都是梅森素数,因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。
梅森素数的探寻难度极大,它不仅需要高深的理论和纯熟的技巧,而且需要进行艰苦的计算。

梅森素数手算笔录时代

在计算能力低下的公元前,人们仅知道四个2p-1型素数:3731127,发现人已无从考证。1456年,又一个没有留下姓名的人在其手稿中给出了第5个2p-1型素数:8191。而在梅森之前,意大利数学家卡塔尔迪(1548~1626)也对这种类型的素数进行了整理,他在1588年提出
也是素数,由此成为第一个在发现者榜单上留名的人。
手算笔录的时代,每前进一步,都显得格外艰难。1772年,在卡塔尔迪之后近200年,瑞士数学家欧拉(1707~1783)在双目失明的情况下,靠心算证明了
是一个素数。这是人们找到的第8个梅森素数,它共有10位数,堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完全数定理的逆定理所有的偶完全数都具有 2p-1(2p-1)的形式,其中2p-1是素数。这表明梅森素数和偶完全数是一一对应的。
100年后,法国数学家卢卡斯(1842~1891)提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理,为梅森素数的研究提供了有力的工具。1876年,卢卡斯证明
是素数,这是人们靠手工计算发现的最大梅森素数,长达39位。
1883年,俄国数学家波佛辛(1827~1900)利用卢卡斯定理证明了
也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数:
,它们分别在1911年与1914年被数学家鲍尔斯(1875~1952)发现。
卢卡斯第一个否定了 “M67为素数” 这一自梅森断言以来一直被人们相信的结论,但他未能找到其因子。直到1903年,才由数学家科尔(1861~1926)算出267-1=193707721×761838257287。1922年,数学家克莱契克(1882~1957)进一步验证了M257并不是素数,而是合数。
在手工计算的漫长年代里,人们历尽艰辛,一共只找到12个梅森素数。

梅森素数计算机时代

20世纪30年代,美国数学家莱默(1905~1991)改进了卢卡斯的工作,给出了一个针对Mp的新的素性测试方法,即卢卡斯-莱默检验法Mp>3是素数当且仅当Lp-2=0,其中L0=4,Ln+1=(Ln2 -2)modMp这一方法在 “计算机时代” 发挥了重要作用。
1952年,美国数学家鲁滨逊(1911~1995)在莱默指导下将此方法编译成计算机程序,使用SWAC型计算机在几个月内,
美国伊利诺伊大学发行的纪念邮戳 美国伊利诺伊大学发行的纪念邮戳
就找到了5个梅森素数:
。其后,
在1957年被黎塞尔(1929~ 2014)证明是素数;
在1961年被赫维兹(1937~ )证明是素数。
1963年,美国数学家吉里斯(1928~1975)证明
是素数。
1963年6月2日晚上8点,第23个梅森素数
通过大型计算机被找到。发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲,以致于把所有从系里发出的信件都敲上了 “211213-1是个素数” 的邮戳。
超级计算机的引入加快了梅森素数的寻找步伐,但随着指数p值的增大,每一个梅森素数的产生反而更加艰难。1971年3月4日晚,塔克曼(1915~2002)使用IBM360-91型计算机找到新的梅森素数
。而到1978年10月,世界几乎所有的大新闻机构(包括中国的新华社)都报道了以下消息:两名年仅18岁的美国高中生诺尔(1960~ )和尼科尔使用Cyber-174型计算机找到了第25个梅森素数
1979年2月,诺尔又独自发现第26个梅森素数
伴随数学理论的改善,为寻找梅森素数而使用的计算机也越来越强大,包括了著名的IBM360型计算机和超级计算机Cray系列。1979年4月,史洛温斯基使用Cray-1型计算机找到梅森素数
。使用经过改进的Cray-XMP型计算机在1982年至1985年间找到了3个梅森素数:
。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。
1988年,科尔魁特和韦尔什使用NEC-SX2型超高速并行计算机果然发现
。沉寂4年之后,哈威尔实验室(英国原子能技术权威机构)的一个研究小组宣布他们找到梅森素数
1994年1月10日,史洛温斯基和盖奇再次夺回发现已知最大素数的桂冠——这一素数是
。而下一个梅森素数
仍是他们的成果,史洛温斯基由于发现7个梅森素数,而被人们誉为 “素数大王” 。1996年发现的M1257787是迄今为止最后一个由超级计算机发现的梅森素数,数学家使用了Cray-T94,这也是人类发现的第34个梅森素数。

梅森素数因特网时代

使用超级计算机寻找梅森素数实在太昂贵了,而且可以参与的人也有限,网格这一崭新技术的出现使梅森素数的搜寻又重新回到了 “人人参与” 的大众时代。20世纪90年代中后期,在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下,建立了世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜索(GIMPS)。人们只要在GIMPS的主页上下载一个计算梅森素数的免费程序,就可以立即参加该项目来搜寻新的梅森素数。
1996年至1998年,GIMPS找到了3个梅森素数:
,其发现者来自法国、英国和美国。
1999年6月1日,美国密歇根州普利茅茨的数学爱好者哈吉拉特瓦拉通过GIMPS项目找到第38个梅森素数
,这是20世纪发现的最后一个梅森素数,也是人们知道的第一个超过100万位的素数。如果把它写下来的话,共有2098960位数字。
柯蒂斯·库珀再次发现“最大素数” 柯蒂斯·库珀再次发现“最大素数”
进入21世纪,随着个人计算机的进一步普及和计算速度的提升,人们又找到不少更大的梅森素数。加拿大志愿者卡梅伦在2001年11月找到
,拉开了新世纪寻找梅森素数的序幕。[2]  此后在2003年至2006年间,GIMPS又相继发现5个梅森素数:
,最大素数纪录离1000万位大关越来越近。[3-7] 
2008年8月23日,美国加州大学洛杉矶分校的计算机专家史密斯终于发现超过1000万位的梅森素数
[8]  它有12978189位数,如果用普通字号将这个巨数连续打印下来,它的长度可超过50公里!这一成就被美国的《时代》杂志评为 “2008年度50项最佳发明” 之一,排名在第29位。[9] 
此后一年内,又有两个1000万位以上的梅森素数被德国和挪威的志愿者先后找出。[10-11] 
距史密斯的发现仅相隔两个星期,而2009年4月找到的
与史密斯发现的素数相比 “仅” 相差14万位数。
2013年1月,美国中央密苏里大学数学教授柯蒂斯·库珀领导的研究小组发现了第48个梅森素数
[12]  这一发现被英国《新科学家》周刊评为当年自然科学十大突破之一。[13]  2016年1月7日,库珀又发现第49个梅森素数 274207281-1。这个超大素数有22338618位,是目前已知的最大素数。这已是库珀第四次通过GIMPS项目发现新的梅森素数。[14] 

梅森素数梅森素数表

编辑
至2016年1月,已经发现49个梅森素数,并且确定M32582657位于梅森素数序列中的第44位。[15]  现把它们的数值、位数、发现时间、发现者等列表如下:

梅森素数M1~M12

序号p梅森素数位数发现时间发现者
3
1
古代
古人
7
1
古代古人
31
2
古代古人
127
3
古代古人
8191
4
1456年
无名氏
131071
6
1588年
Pietro Cataldi
524287
6
1588年
Pietro Cataldi
10
1772年
Leonhard Euler
2305843009213693951
19
1883年
Ivan Mikheevich Pervushin
618970019642690137449562111
27
1911年
Ralph Ernest Powers
162259276829213363391578010288127
33
1914年
Ralph Ernest Powers
170141183460469231731687303715884105727
39
1876年
Édouard Lucas

梅森素数M13~M34

序号p位数发现时间发现者计算机
5211571952 / 01 / 30
Raphael Mitchel Robinson
SWAC
6071831952 / 01 / 30
Raphael Mitchel Robinson
SWAC
1,2793861952 / 06 / 25
Raphael Mitchel Robinson
SWAC
2,2036641952 / 10 / 07
Raphael Mitchel Robinson
SWAC
2,2816871952 / 10 / 09
Raphael Mitchel Robinson
SWAC
3,2179691957 / 09 / 08Hans RieselBESK
4,2531,2811961 / 11 / 03Alexander HurwitzIBM 7090
4,4231,3321961 / 11 / 03Alexander HurwitzIBM 7090
9,6892,9171963 / 05 / 11Donald Bruce GilliesILLIAC II
9,9412,9931963 / 05 / 16Donald Bruce GilliesILLIAC II
11,2133,3761963 / 06 / 02Donald Bruce GilliesILLIAC II
19,9376,0021971 / 03 / 04Bryant TuckermanIBM 360/91
21,7016,5331978 / 10 / 30
Landon Curt Noll & Laura Nickel
CDC Cyber 174
6,9871979 / 02 / 09Landon Curt Noll
CDC Cyber 174
44,49713,3951979 / 04 / 08Harry Lewis Nelson & David SlowinskiCray 1
86,24325,9621982 / 09 / 25David SlowinskiCray 1
110,50333,2651988 / 01 / 28
Walter Colquitt & Luke Welsh
NEC SX-2
39,7511983 / 09 / 20David SlowinskiCray X-MP
216,09165,0501985 / 09 / 06David SlowinskiCray X-MP/24
756,839227,8321992 / 02 / 19
David Slowinski & Paul Gage
Harwell Lab's Cray-2
859,433258,7161994 / 01 / 10
David Slowinski & Paul Gage
Cray C90
1,257,787378,6321996 / 09 / 03
David Slowinski & Paul Gage
Cray T94

梅森素数M35~M49

序号p位数发现时间发现者国家
1,398,269420,9211996 / 11 / 13GIMPS / Joel Armengaud法国
2,976,221895,9321997 / 08 / 24GIMPS / Gordon Spence英国
909,5261998 / 01 / 27GIMPS / Roland Clarkson美国
6,972,5932,098,9601999 / 06 / 01
GIMPS / Nayan Hajratwala
美国
13,466,9174,053,9462001 / 11 / 14
GIMPS / Michael Cameron
加拿大
20,996,0116,320,4302003 / 11 / 17GIMPS / Michael Shafer美国
24,036,5837,235,7332004 / 05 / 15GIMPS / Josh Findley美国
25,964,9517,816,2302005 / 02 / 18GIMPS / Martin Nowak德国
30,402,4579,152,0522005 / 12 / 15GIMPS / Curtis Cooper & Steven Boone美国
32,582,6579,808,3582006 / 09 / 04GIMPS / Curtis Cooper & Steven Boone美国
45*37,156,667
11,185,272
2008 / 09 / 06
GIMPS / Hans-Michael Elvenich
德国
46*42,643,80112,837,0642009 / 04 / 12
GIMPS / Odd Magnar Strindmo
挪威
47*43,112,60912,978,189
2008 / 08 / 23
GIMPS / Edson Smith美国
48*
57,885,16117,425,1702013 / 01 / 25GIMPS / Curtis Cooper美国
49*
74,207,28122,338,6182016 / 01 / 07GIMPS / Curtis Cooper美国
注:
  1. 各表分别列出人工、借助计算机以及通过GIMPS项目发现的梅森素数。
  2. 目前还不确定在M44和M49之间是否还存在未知的梅森素数,其后的序号用 * 标出。
  3. 后两表梅森素数的数值从略。

梅森素数分布规律

编辑
人们在寻找梅森素数的同时,对其重要性质——分布规律的研究也在进行着。从已发现的梅森素数来看,它们在正整数中的分布时疏时密、极不规则;从发现梅森素数的时间来看,有时许多年未能找到一个,而有时则一下找到好几个。梅森素数已发现的数量很少,且人们对其无穷性尚未可知,因此探索它的分布规律似乎比寻找新的梅森素数更为困难。数学家们在长期的摸索中,提出了一些猜想,英国数学家香克斯、美国数学家吉里斯、法国数学家托洛塔和德国数学家伯利哈特曾分别给出过关于梅森素数分布的猜测。但他们的猜测有一个共同点,就是都以近似表达式给出,而它们与实际情况的接近程度均未尽如人意。
梅森素数的分布规律(周氏猜测)
梅森素数的分布规律(周氏猜测) (3张)
中国学者周海中根据已知的梅森素数及其排列,巧妙地运用联系观察法和不完全归纳法,于1992年2月正式提出了一个关于梅森素数分布的猜想,并首次给出其分布的精确表达式。[16]  后来这一重要猜想被国际数学界命名为 “周氏猜测” 。周氏猜测的基本内容为:当
时,Mp2n+1-1个是素数;即
时梅森素数的个数为2n+2-n-2周氏猜测自提出以来一直受到人们关注,而且在一些国内外出版的数学辞典和教科书中都有介绍。美籍挪威数论大师、菲尔茨奖沃尔夫奖得主阿特勒·塞尔伯格认为:周氏猜测具有创新性,开创了富于启发性的新方法;其创新性还表现在揭示新的规律上。[17] 
周氏猜测的表达式虽然简单,但破解这一猜测的难度却很大。就目前研究文献来看,一些数学家和数学爱好者尝试破解周氏猜测,却至今未能证明或反证。

梅森素数GIMPS项目

编辑
1996年初,美国数学家和程序设计师乔治·沃特曼编制了一个名为Prime95的梅森素数计算程序,并把它放在网页上供数学家和数学爱好者免费使用,这就是著名的 “因特网梅森素数大搜索”(GIMPS)项目。该项目采取网格计算方式,利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。1997年美国数学家及程序设计师斯科特·库尔沃斯基和其他人建立了 “素数网”(PrimeNet),使分配搜索区间和向GIMPS发送报告自动化。一个庞大的数据库记录着所有任务的分配情况和计算报告,如果某个交回的计算报告显示发现了一个新的梅森素数,还需经过一个独立机构用另一套程序验证才能被正式确认。
EFF向获奖者(右一)颁发奖金 EFF向获奖者(右一)颁发奖金
为了激励人们寻找梅森素数和促进网格技术发展,总部设在美国的电子前沿基金会(EFF)于1999年3月向全世界宣布了为通过GIMPS项目来寻找新的更大的梅森素数而设立的奖金。它规定向第一个找到超过100万位数的个人或机构颁发5万美元。后面的奖金依次为:超过1000万位数,10万美元;超过1亿位数15美元超过10亿位数25美元[18]  除此之外,根据EFF关于奖金设立的新规定,任何一位新梅森素数的发现者都将获得3000美元的奖励。其实绝大多数志愿者参与该项目并不是为了金钱,而是出于乐趣、荣誉感和探索精神。
目前人们通过GIMPS项目已找到15个梅森素数,其发现者来自美国(9个)、英国(1个)、法国(1个)、德国(2个)、加拿大(1个)和挪威(1个)。世界上有190多个国家和地区超过60万人参加了这一国际合作项目,并动用了上百万台计算机(CPU)联网来寻找新的梅森素数。[19]  该项目的计算能力已超过当今世界上任何一台最先进的超级矢量计算机的计算能力,运算速度达到每秒2300万亿次。著名的《自然》杂志说:GIMPS项目不仅会进一步激发人们对梅森素数寻找的热情,而且会引起人们对网格技术应用研究的高度重视。

梅森素数意义

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

梅森素数大事记

编辑
  • 公元前4世纪,古希腊数学家欧几里得在《几何原本》第九章中论述了完全数与2p-1型素数的关系,并提出有少量素数可表示成2p-1(p为素数)的形式,由此开创了研究2p-1型素数的先河。
  • 15世纪,发现第5个2p-1型素数。
  • 16世纪,意大利数学家卡塔尔迪开始对此类素数进行整理。
  • 17世纪,法国数学家马林·梅森的工作成为2p-1型素数研究的转折点和里程碑之一,“梅森素数” 也由此得名。
  • 18世纪,瑞士数学家欧拉证明了完全数定理的逆定理,并心算出第8个梅森素数M31,是当时已知的最大素数。
  • 19世纪70年代,法国数学家卢卡斯提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理,并证明了M127是一个素数。卢卡斯的工作为梅森素数的研究提供了有力的工具。
  • 19世纪末至20世纪初,数学家利用卢卡斯定理又陆续证明M61、M89、M107是素数。人类在 “手算笔录时代” 共发现12个梅森素数。
  • 20世纪30年代,美国数学家莱默改进了卢卡斯的工作,给出了一个针对Mp的新的素性测试方法,即卢卡斯-莱默检验法。此方法在 “计算机时代” 发挥了重要作用,时至今日仍是检测梅森数素性的最佳方法。
  • 电子计算机的发明革命化的改进了梅森素数的寻找,仅在1952年就找到5个梅森素数。此后为寻找梅森素数而使用的计算机功能也越来越强大。
  • 1992年,中国学者周海中提出了一个关于梅森素数分布的猜想,并首次给出其分布的精确表达式。这一猜想在国际数学界引起较大反响,被命名为 “周氏猜测” 。
  • 1996年,著名的 “因特网梅森素数大搜索”(GIMPS)项目建立,加快了寻找更大梅森素数的进程。
  • 1999年3月,美国电子前沿基金会(EFF)向全世界宣布了为寻找更大的梅森素数而设立的奖金。至2008年8月,已发现超过1000万位的梅森素数。
词条图册 更多图册
参考资料
词条标签:
科技术语 科学 数学 学科