网站地图
梅森素数

梅森素数是由梅森数而来。

所谓梅森数,是指形如2p-1的一类数,其中指数p是素数,常记为Mp 。如果梅森数是素数,就称为梅森素数。

用因式分解法可以证明,若2n-1是素数,则指数n也是素数;反之,当n是素数时,2n-1(即Mp)却未必是素数。前几个较小的梅森数大都是素数,然而梅森数越大,梅森素数也就越难出现。

目前仅发现51个梅森素数,最大的是M82589933(即2的82589933次方减1),有24862048位数。

素数是指在大于1的整数中只能被1和其自身整除的数。素数有无穷多个,但到2018年底却只发现有51个素数能表示成2p-1(p为素数)的形式,这就是梅森素数(如3、7、31、127等等)。它是以17世纪法国数学家马林梅森的名字命名。

梅森素数是数论研究中的一项重要内容,自古希腊时代起人们就开始了对梅森素数的探索。由于这种素数具有着独特的性质(比方说和完全数密切相关)和无穷的魅力,千百年来一直吸引着众多数学家(包括欧几里得、费马、欧拉等)和无数的数学爱好者对它进行探究。

在现代,梅森素数在计算机科学、密码学等领域有重要的应用价值。它还是人类好奇心、求知欲和荣誉感的最好见证。

早在公元前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多年来,人类仅发现51个梅森素数,由于这种素数珍奇而迷人,因此被人们誉为 “数海明珠” 。自梅森提出其断言后,人们发现的已知最大素数几乎都是梅森素数,因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。

梅森素数的探寻难度极大,它不仅需要高深的理论和纯熟的技巧,而且需要进行艰苦的计算。

在计算能力低下的公元前,人们仅知道四个2p-1型素数:3731127,发现人已无从考证。15世纪,又一个没有留下姓名的人在其手稿中给出了第5个2p-1型素数:8191。而在梅森之前,意大利数学家卡塔尔迪(1548~1626)也对这种类型的数进行了整理,他在1588年提出131071524287也是素数,由此成为第一个在发现者榜单上留名的人。

手算笔录的时代,每前进一步,都显得格外艰难。1772年,在卡塔尔迪之后近200年,瑞士数学家欧拉(1707~1783)在双目失明的情况下,靠心算证明了2147483647是一个素数。这是人们找到的第8个梅森素数,它共有10位数,堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完全数定理的逆定理:所有的偶完全数都具有2p-1(2p-1) 的形式,其中2p-1是素数。这表明梅森素数和偶完全数是一一对应的。

100年后,法国数学家卢卡斯(1842~1891)提出了一个用来判别Mp是否为素数的重要定理卢卡斯定理,为梅森素数的研究提供了有力的工具。 [2] 1876年,卢卡斯证明

1883年,俄国数学家波佛辛(1827~1900)利用卢卡斯定理证明了

卢卡斯第一个否定了 “M67为素数” 这一自梅森断言以来一直被人们相信的结论,但他未能找到其因子。直到1903年,才由数学家科尔(1861~1926)算出M67=193707721×761838257287。1922年,数学家克莱契克(1882~1957)进一步验证了M257并不是素数,而是合数。

在手工计算的漫长年代里,人们历尽艰辛,一共只找到12个梅森素数。

20世纪30年代,美国数学家莱默(1905~1991)改进了卢卡斯的工作,给出了一个针对Mp的新的素性测试方法,即卢卡斯-莱默检验法:Mp>3是素数当且仅当Lp-2=0,其中L0=4,Ln+1=(Ln2-2)modMp [2] 这一方法在 “计算机时代” 发挥了重要作用。

1952年,美国数学家鲁滨逊(1911~1995)在莱默指导下将此方法编译成计算机程序,使用SWAC型计算机在几个月内,就找到了5个梅森素数:

1963年,美国数学家吉里斯(1928~1975)证明

1963年6月2日晚上8点,第23个梅森素数

以IBM360为代表的第三代计算机的出现加快了梅森素数的寻找步伐,但随着指数p值的增大,每一个梅森素数的产生反而更加艰难。1971年3月4日晚,塔克曼(1915~2002)使用IBM360-91型计算机找到新的梅森素数

1979年2月,诺尔又独自发现第26个梅森素数

伴随数学理论的改善,为寻找梅森素数而使用的计算机也越来越强大,其中包括了著名的超级计算机Cray系列。1979年4月,美国克雷公司计算机专家史洛温斯基使用Cray-1型计算机找到梅森素数

1988年,科尔魁特和韦尔什使用NEC-SX2型超高速并行计算机果然发现

1994年1月10日,史洛温斯基和盖奇再次夺回发现已知最大素数的桂冠这一素数是

使用超级计算机寻找梅森素数实在太昂贵了,而且可以参与的人也有限,网格这一崭新技术的出现使梅森素数的搜寻又重新回到了 “人人参与” 的大众时代。20世纪90年代中后期,在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下,建立了世界上第一个基于互联网的分布式计算项目因特网梅森素数大搜索(GIMPS)。人们只要在GIMPS的主页上下载一个计算梅森素数的免费程序,就可以立即参加该项目来搜寻新的梅森素数。

1996年至1998年,GIMPS找到了3个梅森素数:

1999年6月1日,美国密歇根州普利茅茨的数学爱好者哈吉拉特瓦拉通过GIMPS项目找到第38个梅森素数

进入21世纪,随着个人计算机的进一步普及和计算速度的提升,人们又找到不少更大的梅森素数。加拿大青年志愿者卡梅伦在2001年11月找到

2008年8月23日,美国加州大学洛杉矶分校的计算机专家史密斯终于发现超过1000万位的梅森素数

此后一年内,又有两个1000万位以上的梅森素数被德国和挪威的志愿者先后找出。 [11-12]

2013年和2016年,美国中央密苏里大学数学教授柯蒂斯库珀利用校区内的800台电脑连续发现了两个梅森素数

2017年12月26日,51岁的美国志愿者乔纳森佩斯找到了第50个已知的梅森素数

2018年4月8日,在发现M43112609超过9年后,该数已被确定为第47个梅森素数。 [18]

至2018年12月,总计发现51个梅森素数,并且确定M43112609位于梅森素数序列中的第47位。现把它们的数值、位数、发现时间、发现者等列表如下:

2

3

1

古代

古人

3

7

1

5

31

2

7

127

3

13

8191

4

1456年

无名氏

17

131071

6

1588年

Pietro Cataldi

19

524287

6

1588年

Pietro Cataldi

31

2147483647

10

1772年

Leonhard Euler

61

2305843009213693951

19

1883年

Ivan Mikheevich Pervushin

89

618970019642690137449562111

27

1911年

Ralph Ernest Powers

107

162259276829213363391578010288127

33

1914年

Ralph Ernest Powers

127

170141183460469231731687303715884105727

39

1876年

douard Lucas

Raphael MitchelRobinson

Raphael MitchelRobinson

Raphael MitchelRobinson

Raphael MitchelRobinson

Raphael MitchelRobinson

Landon Curt Noll &Laura Nickel

CDC Cyber174

23,209

CDC Cyber174

Walter Colquitt &Luke Welsh

132,049

David Slowinski &Paul Gage

David Slowinski &Paul Gage

David Slowinski &Paul Gage

3,021,377

GIMPS / NayanHajratwala

GIMPS / MichaelCameron

11,185,272

GIMPS / Hans-MichaelElvenich

GIMPS / Odd MagnarStrindmo

2008 / 08 / 23

注:
  1.各表分别列出人工、借助计算机以及通过GIMPS项目发现的梅森素数。
  2.目前还不确定在M47和M51之间是否还存在未知的梅森素数,其后的序号用 * 标出。
  3.后两表梅森素数的数值从略。

1996年初,美国数学家和程序设计师乔治沃特曼(George Woltman)编制了一个名为Prime95的梅森素数计算程序,并把它放在网页上供数学家和数学爱好者免费使用,这就是著名的 “因特网梅森素数大搜索”(GIMPS)项目。该项目采取网格计算方式,利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。1997年美国数学家及程序设计师斯科特库尔沃斯基(Scott Kurowski)和其他人建立了 “素数网”(PrimeNet),使分配搜索区间和向GIMPS发送报告自动化。一个庞大的数据库记录着所有任务的分配情况和计算报告,如果某个交回的计算报告显示发现了一个新的梅森素数,还需经过一个独立机构用另一套程序验证才能被正式确认。

为了激励人们寻找梅森素数和促进网格技术发展,总部设在美国旧金山的电子前沿基金会(EFF)于1999年3月向全世界宣布了为通过GIMPS项目来寻找新的更大的梅森素数而设立的奖金。它规定向第一个找到超过100万位数的个人或机构颁发5万美元。后面的奖金依次为:超过1000万位数,10万美元;超过1亿位数,15万美元;超过10亿位数,25万美元。 [19] 除此之外,根据EFF关于奖金设立的新规定,任何一位新梅森素数的发现者都将获得3000美元的研究发现奖。其实绝大多数志愿者参与该项目并不是为了金钱,而是出于乐趣、荣誉感和探索精神。

目前人们通过GIMPS项目已找到17个梅森素数,其发现者来自美国(11个)、英国(1个)、法国(1个)、德国(2个)、加拿大(1个)和挪威(1个)。世界上有190多个国家和地区超过60万人参加了这一国际合作项目,并动用了上百万台计算机(CPU)联网来寻找新的梅森素数。 [20] 该项目的计算能力已超过当今世界上任何一台最先进的超级矢量计算机的计算能力,运算速度达到每秒2300万亿次。著名的《自然》杂志说:GIMPS项目不仅会进一步激发人们对梅森素数寻找的热情,而且会引起人们对网格技术应用研究的高度重视。

梅森素数自古以来就是数论研究的一项重要内容,历史上有不少大数学家都专门研究过这种特殊形式的素数。自古希腊时代起直至17世纪,人们寻找梅森素数的意义似乎只是为了寻找完全数。但自梅森提出其著名断言后,特别是欧拉证明了欧几里得关于完全数定理的逆定理以来,偶完全数已仅仅是梅森素数的一种 “副产品” 了。

寻找梅森素数在当代已有了十分丰富的意义。寻找梅森素数是目前发现已知最大素数的最有效途径。自欧拉证明M31为当时最大的素数以来,在发现已知最大素数的世界性竞赛中,梅森素数几乎囊括了全部冠军。

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

寻找梅森素数最新的意义是:它促进了分布式计算技术的发展。从最新的17个梅森素数是在因特网项目中发现这一事实,可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能,这是一个前景非常广阔的领域。它的探究还推动了快速傅立叶变换的应用。

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

由于梅森素数的探究需要多种学科和技术的支持,也由于发现新的 “大素数” 所引起的国际影响,使得对于梅森素数的研究能力已在某种意义上标志着一个国家的科技水平,而不仅仅是代表数学的研究水平。英国顶尖科学家、牛津大学教授马科斯索托伊甚至认为它的研究进展不但是人类智力发展在数学上的一种标志,同时也是整个科学发展的里程碑之一 [21]

梅森素数这颗数学海洋中的璀璨明珠正以其独特的魅力,吸引着更多的有志者去寻找和研究。

梅森素数的计算公式

3*5/3.8*7/5.8*11/9.8*13/11.8*......*P/(P-1.2)-1=M

P是梅森数的指数,M是P以下的梅森素数的个数。

以下是计算的数值与实际数的情况:

指数5,计算2.947,实际3 ,误差0.053;

指数7,计算3.764,实际4 ,误差 0.236;

指数13,计算4.891,实际5,误差0.109;

指数17,计算5.339,实际6,误差0.661;

指数19,计算5.766,实际7,误差1.234;

指数31,计算6.746,实际8,误差1.254;

指数61,计算8.445,实际9,误差0.555;

指数89,计算9.201,实际10,误差0.799;

指数107,计算9.697,实际11,误差1.303;

指数127,计算10.036 ,实际12,误差1.964;

指数521,计算13.818,实际13,误差-0.818;

指数607,计算14.259,实际14,误差-0.259;

指数1279,计算16.306,实际15,误差-1.306;

指数2203,计算17.573,实际16,误差-1.573;

指数2281,计算17.941,实际17,误差-0.941;

这个公式是根据梅森素数的分布规律得出的。万数1为首,1被除外了,所以要减去1。在不考虑重叠问题,应该P减1就可以了,这里已考虑重叠问题,所以就P减1.2.在梅森数的指数渐渐增大,1.2是否合适,还要等实际检验。

所有的奇素数都是准梅森数(2^N-1)的因 子数,则梅森合数的因子数是只有素数中的一部份。

在2^N-1的数列中,一个素数作为素因子第一次出现在指数N的数中,这个素数作为因子数在2^N-1数列中就以N为周期出现。在这种数列中指数是偶数的都等于3乘以四倍金字塔数。

在2^N-1数列中,指数大于6的,除梅森素数外,都有新增一个或一个以上的素数为因子数,新增的因子数减1能被这个指数整除。

一个梅森合数的因子数只有唯一一次出现在一个梅森合数中。

一个是梅森素数的素数,它永远不是梅森合数的因子数。

一个是前面的梅森合数的因子数的素数,它永远不会是后面的梅森合数的因子数。

所有梅森合数的因子数减1都能被这个梅森合数的指数整除,商是偶数。

一个素数在不是梅森合数的准梅森数中第一次以因子数出现,这个素数减1能被这个准梅森数的指数整除,商不一定是偶数。

梅森素数都在[4^(1-1)+4^(2-1)+4^(3-1)+......+4^(n-1)]*6+1数列中,括符里种数暂叫四倍金字塔数。

凡是一个素数是四倍金字塔数的因子数,以后就不是梅森合数的因子数。

在4^(1-1)+4^(2-1)+4^(3-1)+......+4^(n-1)数列中的数,有不等于6NM+-(N+M)的数乘以6加上1都是梅森素数。

在2^P-1平方根以下的素数都以素因子在以前准梅森数中出现了,那这个梅森数必是梅森素数。但它的逆定理是不成立的。如果还没有出现在以前的准梅森数中的素数,它也不定是梅森合数的因子数。

梅森合数的因子数都是8N+1和8N-1形的素数。

试证梅森素数

在指数n是无限多的2^n-1数列中梅森数和梅森素数只占其中的很少比例。

根据费马小定理,每一个奇素数都会以数因子出现在2^n-1数列中,只不过有些提前出现,有些最后出现。只有梅森素数是最早出现在这个数列中的。其他有素数都不会最早出现,最迟出现的素数是在本数减1的数中,也就是费马小定理的地方。

每一个奇素数都十分有规律作为因子数出现在2^n-1数列中,一个素数第一次出现在2^n-1数中(包括梅森素数),这个素数就以n为周期反复出现在2^n-1数列中,如3第一次出现在n=2中,指数能被2整除的都有3的因子数;7第一次出现在n=3,指数能被3整除的都有7的因子数;5第一次出现在n=4中,指数能被4整除都有5的因子数。一个素数出现在2^n-1数列n中,不管n是素数不是素数,只要用小于n的全部奇素数去筛,指数n都在其中。如果是合数与前面的素数是重叠的,所以不用重筛了。

要筛完2^n-1数列中所有数因子,必需用少于或等于2^n-1平方根以内的所有素数去筛,这样剩下没有筛的就是梅森素数了。

2^n-1的数列是无限多的,无限多的自然数任你筛多少次的几分之一,永远是无限多的。所以梅森素数是无限多的。

梅森素数的筛法

根据费马小定理,每一个奇素数都会以素因子的身份出现在2^n-1数列中,只不过有些出现早,有些出现迟。

每一个奇素数第一次出现在2^n-1数列指数n的数中,这个n就是这个素数的对应数,它就以n为周期反复出现。

已经知道梅森素数都出现在梅森数中。只要筛去梅森数中的梅森合数,剩下就是梅森素数。

将梅森数列展开,从3的对应数2开始,2点一点;5的对应数是4,4是合数,就不用操作;7的对应数是3,在3点一点;11的对应数是10,是合数,不用操作;13的对应数是12,12是合数,不用操作;这样一直点下去,点到梅森数的指数以前的数都能筛净。凡是一个梅森数点上两次和两次以上的都给划去,剩下就是只有点一次的梅森数了,这些梅森数全是梅森素数。

这个筛法在素数很大时找它的对应数有点困难。


相关文章推荐:
梅森数 | 梅森数 | 梅森数 | 素数 | 因式分解法 | 素数 | 梅森数 | 素数 | 整数 | 马林梅森 | 数论 | 古希腊 | 计算机科学 | 密码学 | 好奇心 | 求知欲 | 荣誉感 | 欧几里得 | 几何原本 | 完全数 | 费马 | 马林梅森 | 法兰西学院 | 合数 | 转折点 | 梅森数 | 梅森素数 | 最大素数 | 3 | 7 | 31 | 127 | 81 | 91 | 13 | 107 | 1 | 5 | 2 | 42 | 87 | 欧拉 | 2147483647 | 逆定理 | 素数 | 莱默 | 素性测试 | 卢卡斯-莱默检验法 | 计算机程序 | 大型计算机 | 伊利诺伊大学 | 第三代计算机 | 超级计算机 | 原子能 | 桂冠 | 网格 | GIMPS | 密歇根州 | 个人计算机 | 加州大学洛杉矶分校 | 时代 | 中央密苏里大学 | 2 | 3 | 5 | 7 | 13 | 17 | 19 | 31 | 61 | 89 | 107 | 127 | 521 | 607 | 1 | 27 | 9 | 2 | 20 | 3 | 2 | 2 | 81 | 3 | 21 | 7 | 4 | 253 | 4 | 4 | 23 | 9 | 6 | 89 | 9 | 941 | 11 | 213 | 19 | 9 | 37 | 21 | 701 | 23 | 209 | 44 | 49 | 7 | 86 | 243 | 110 | 503 | 132 | 0 | 49 | 216 | 0 | 91 | 756 | 8 | 39 | 8 | 59 | 4 | 33 | 1 | 257 | 78 | 7 | 1 | 3 | 98 | 26 | 9 | 2 | 97 | 6 | 22 | 1 | 3 | 0 | 21 | 377 | 6 | 9 | 72 | 5 | 93 | 13 | 4 | 66 | 91 | 7 | 20 | 996 | 0 | 11 | 24 | 0 | 36 | 58 | 3 | 25 | 96 | 4 | 95 | 1 | 30 | 40 | 2 | 4 | 57 | 32 | 5 | 82 | 65 | 7 | 37 | 156 | 6 | 67 | 42 | 6 | 43 | 80 | 1 | 43 | 112 | 60 | 9 | 57 | 88 | 5 | 16 | 1 | 74 | 207 | 2 | 81 | 77 | 23 | 2 | 91 | 7 | 82 | 5 | 8 | 9 | 9 | 3 | 3 | 乔治沃特曼 | Prime95 | 网格计算 | 网格技术 | 电子前沿基金会 | 超过 | 1 | 亿 | 位数 | | 15 | | 美元 | | 超过 | 10 | 亿 | 位数 | | 25 | | 美元 | | CPU | 自然 | 网格技术 | 完全数 | 运算速度 | 克雷 | 数值计算 | 计算数学 | 分布式计算 | 快速傅立叶变换 | 牛津大学 |
相关词汇词典