有没有最大素数(一名程序员意外发现迄今最大素数)(1)

让我数数

这到底是几个0

在上周,一名来自美国佛罗里达州的程序员Patrick Laroche,利用互联网的梅森素数大搜索项目(GIMPS),发现了迄今为止人类发现的最大素数282589933-1!

它有它一共有24862048 位数字,作为人类发现的第 51 个梅森素数,它被命名为M82589933。 因此Patrick Laroche也获得了 3000 美元的奖金。

有没有最大素数(一名程序员意外发现迄今最大素数)(2)

图丨迄今最大素数(来源:GIMPS )

短短不到一年的时间,想不到就发现了第51位梅森素数素数。

2017年的12月,第50位素数被发现。美国一位普通的电气工程师Jonathan Pace,在他成为GIMPS计划志愿者的第14个年头,找到第50个梅森素数,即277232917-1,这是目前为止人类发现的最大素数,共计23249425位。

还记得当时,第50个梅森素数诞生后的两周后,日本虹色社还很丧心病狂的发行了一本书,名叫《2017年最大的素数》(『2017年最大の素数』),厚约32mm,共719页,整本书只印了一个数,第50个梅森素数。

有没有最大素数(一名程序员意外发现迄今最大素数)(3)

《2017年最大的素数》内页,里面密密麻麻都是数字

虽然数学类书籍向来不是那么好卖,但是,这本书在发行两周后却迅速攀上日本亚马逊数学类“畅销书第1位”,卖到断货!

有没有最大素数(一名程序员意外发现迄今最大素数)(4)

可能对于读者来说,把这本书买回家,精神意义远大于实际意义。

毕竟自17世纪法国数学家马林·梅森(Marin Mersenne)开始,人们就开始不断寻找梅森素数。找到第50个梅森素数,是数学领域的重大发现,也是人类发展一个新的里程碑。

这本书更多的是一种信仰,代表人类力求不断进步,勇攀高峰的精神

有没有最大素数(一名程序员意外发现迄今最大素数)(5)

可能看到这里,就会有人要问了,为什么科学家们这么热衷于寻找素数?素数到底有什么用?现在小天给大家聊聊关于素数的一切。

素数是什么

素数定义为大于1的自然数中,除了1和它本身以外不再有其他因数。

这个定义很容易理解,以小于10的自然数为例,2、3、5、7是素数,比如7只能被分解为1乘以7,没有其他分解方式。对于其他数来说,比如8可以被分解为2×4,所以8不能是素数。

之所以科学家们热衷于寻找素数。一方面,是对于自身理想的追求,孜孜不倦地在数学的高峰上攀登。但另一方面,素数在实际场景当中却体现很大的价值。

  • 1、计算机领域

素数在计算机领域当中的应用,莫过于信息的加密,其中有著名的RSA算法(小智以前写过RSA算法的介绍,点击传送门)。由于目前大整数的因式分解,即寻找一个大整数的素数因子,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。也就是说,只要密钥长度足够长,寻找素数因子的时间则非常长,用RSA加密的信息实际上是不能被解破的。因此,素数在密码学当中有重要的地位。

有没有最大素数(一名程序员意外发现迄今最大素数)(6)

只有拥有钥匙(私钥)的情况下,才能解出信息

  • 2、工业领域

在汽车变速箱齿轮的设计上,相邻的两个大小齿轮齿数可以设计成素数,以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数,可增强齿轮的耐用度,减少故障。

有没有最大素数(一名程序员意外发现迄今最大素数)(7)

汽车序列式变速箱的细节图

  • 3、生物领域

北美的周期蝉(Magicicada)有着奇特的生命周期。它们要经过一段漫长的时间,每13或17年,才会成群地破土而出。

自17世纪中叶起,科学家就一直对周期蝉的生命周期困惑不已。它们遵循着相同的基本生命周期:幼虫在地底生活13或17年,然后在夏季大量出现。它们爬上树,蜕皮,成长为成虫,然后在短短数周内,成虫相遇、交配、产卵。孵化后,幼虫会回到地底,等待下一个轮回。

为什么是13或者17年,而不是其他数字,而恰好这个数字是素数?

当这些周期蝉大量出土繁殖时,周期蝉的天敌大吃特吃,天敌有更多的营养进行繁殖,天敌数量将会大大增加。假设天敌是6年才能性成熟,它的后代又要6年之后才会性成熟繁殖,因为没有周期蝉吃,它们的数量一直是回落的。再假设周期蝉的周期是18年,那么天敌们将在第18年继续大吃特吃,在这个18年周期内产生了更多的天敌,这样每过18年,天敌的总数不断上涨,周期蝉的数量就越来越少了。同理,周期是16年的周期蝉,很可能会被周期为2、4、8年的天敌吃到绝种。

而13年蝉和17年蝉刚好避过了这些可能性,因为13和17是素数,除非天敌每年繁殖,或者刚好13或17年繁殖,否则不可能成为帮助天敌进行繁殖。因为13年蝉和17年蝉选择了素数的生命周期,大幅度降低了帮助天敌繁殖的机会,使得自己能够生存到今天。(大自然可真神奇)

有没有最大素数(一名程序员意外发现迄今最大素数)(8)

密密麻麻的趴在栅栏上的周期蝉

数学之美,无处不在。就以素数这个特性而言,一方面,人类在计算机的加密算法上,运用到了素数分布的特性;另一方面,大自然按照既定的规律自然运行,却也产生素数周期的特性,素数周期的生物产生了最大的适应性,实在令人惊叹。这让人联想到,诸如蕴含费波那契数列的松果,具有分形结构的山川河流(传送门),与其说这是自然界的神工鬼斧,倒不如说,这是数学规律幕后主使的结果。

有没有最大素数(一名程序员意外发现迄今最大素数)(9)

松果顺时针8环,逆时针13环,这正是费波那契数列当中的数字

数学家对素数干了什么?

素数如同数字的原子一样,是构造其他数字的基石。自然数是无限个,那么作为基石的素数到底有多少个呢?

这个问题在2300多年前得到了解答:素数有无穷多个。古希腊数学家欧几里得在《几何原本》中给出了简洁漂亮的证明。

虽然素数有无穷多个,但要发现和验证大素数却不容易,这就是素数的秘密。有多不容易呢?

有没有最大素数(一名程序员意外发现迄今最大素数)(10)

我们可以很快地把50以内的素数列举出来:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47……

它们看起来很密集,但随着素数越大,它们之间的距离渐渐变长。

重要的是,它们的分布距离是不均等的。要找到一个大的素数,往往需要巨量的计算,要分解和验证它也是这样。为了掌握素数的规律,数学家绞尽脑汁。

其中,有两个关于素数的著名猜想:

孪生素数猜想:存在无限多组之差为2的素数对。哥德巴赫猜想:所有的偶数都可以表示为两个素数之和。

这两个猜想在数学史上非常有名,千百年来许多数学家梦寐以求希望亲手攻克的难题。可喜的是,在最近的100年,这两个猜想得到了重大的突破。

有没有最大素数(一名程序员意外发现迄今最大素数)(11)

张益唐教授

其中,中国数学家张益唐在2012年成功地证明了存在无数对孪生素数,而且其中每一对中的两个素数之差,不超过7000万。虽然只有把7000万降到2才能最终证明孪生素数猜想,但他突破性地把孪生素数的距离,从无限变成了有限。

在张益唐取得这一突破之后,不少学者尝试用他的方法缩小间隔,进一步拉近了与最终解决孪生素数猜想的距离。在2014年2月, 7000万已被缩小至246。

另一方面,中国数学家陈景润在1966年成功证明了“1 2”的成立,距离哥德巴赫猜想“1 1”的成立仅一步之遥。

这里引入一个概念叫殆素数,殆素数是素因子个数不多的正整数。假设N是偶数,虽然目前不能证明N是两个素数之和,但足以证明它能够写成两个殆素数的和,即N=A B,其中A和B的素因子个数都不太多,譬如说素因子个数不超过10。我们可以用“a b”来表示如下命题:每个大偶数N都可表为A B,其中A和B的素因子个数分别不超过a和b。显然,哥德巴赫猜想就可以写成"1 1"。在这一方向上的进展都是用所谓的筛法得到的。自从1920年挪威数学家布朗(Brun)证明了“9 9”以来,这个公式在各大数学家手上不断进行简化,在1966年由我国数学家陈景润证明了“1 2”。

素数寻找计划——GIMPS

素数当中,有一类素数非常特别,形如2p-1,17世纪法国数学家马林·梅森对它进行了深入研究。为了纪念梅森的贡献,学界把这种数称之为梅森数,如果梅森数为素数,则称之为梅森素数

有没有最大素数(一名程序员意外发现迄今最大素数)(12)

马林梅森

在只能手工计算的时代,人们就开始了对梅森素数的寻找,直到19世纪末,人们只找到了12个梅森素数。p值分别是:2,3,5,7,13,17,19,31,61,89,107,127

在计算机诞生以后,人们搜索梅森素数的速度加快,直到1996年为止,数学家使用了超级计算机Cray-T94,发现了第34个梅森素数。

进入互联网时代,一个更加精妙的方法诞生了。1996年1月,美国数学家及程序设计师乔治·沃特曼(George Woltman)编写了一个梅森素数计算程序。他把程序放在网页上供数学家和数学爱好者免费使用,这就是最初的互联网梅森素数大搜索计划了(Great Internet Mersenne Prime Search,GIMPS)。任何拥有个人电脑的人都可以加入GIMPS,成为一名素数猎人

从1997年至今,所有新的梅森素数都是通过GIMPS分布式计算项目发现的。这个项目成功聚集了数十万台计算机进行一个问题的计算,它的计算能力已经远远超出我们的想象。

其中,最新第50个梅森素数的发现,就是美国一位普通的电气工程师Jonathan Pace,用一台普通的家庭计算机CPU型号是i5-6600,幸运地通过GIMPS发现了这个梅森素数,不仅在数学史上留下了自己的名字,而且得到了3000美元的奖励。(大家如果有兴趣,可以下载一个试试,第一个找到超过1亿位数梅森素数的人,奖励15万美元)

有没有最大素数(一名程序员意外发现迄今最大素数)(13)

素数的寻找方法

素数行踪不定,分布未知,怎么样才能找到素数?

在公元前2世纪希腊数学家埃拉托斯特尼(Eratosthenes),就已经提出了一个非常简单而且有效的素数筛法,我们称之为埃拉托斯特尼筛法(Sieve of Eratosthenes)。核心是:要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数

有没有最大素数(一名程序员意外发现迄今最大素数)(14)

一个埃拉托斯特尼筛法的例子

具体的筛法如下:

第1步:确定需要筛选素数的范围,确定范围的最大值,比如是120。第2步:根号120的结果为10.95,所以只需要利用11以内所有素数的倍数来剔除120以内的数字,剩下的就是素数。首先剔除以2为倍数的数字,11以内剔除掉4,6,8,10这几个数字,同时剔除掉120以内所有以2为倍数的数字。第3步:最小的未被剔除的数字为3,剔除以3为倍数的数字,11以内剔除9这个数字,同时剔除掉120以内所有以3为倍数的数字。第4步:最小的未被剔除的数字为5,剔除以5为倍数的数字,11以内不需要剔除数字,同时剔除掉120以内所有以5为倍数的数字。……如此类推,可以将120以内的所有素数完全找到。

不得不说,古人的智慧实在是太让人佩服。

普及完素数知识,超模君忽然发现,第50和51位梅森素数都是在12月被发现!

而新的一年即将到来,是否第52位梅森素数将被发现了? 就让我们拭目以待吧。

有没有最大素数(一名程序员意外发现迄今最大素数)(15)

,