炼数成金 门户 科学探索 数学 查看内容

你知道怎么样才能找到一个素数吗?

2018-3-2 14:29| 发布者: 炼数成金_小数| 查看: 10268| 评论: 0|来自: 网易新闻

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

算法 计算机 数学 超级计算 科学探索

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

紧接着,2018年年初,又发生了一件与之相关的趣闻。

在第50个梅森素数诞生后的两周后,日本虹色社紧急发行了一本书,名叫《2017年较大的素数》(『2017年较大の素数』),厚约32mm,共719页,整本书只印了一个数,第50个梅森素数。

数学类书籍向来不是那么好卖,但是,这本书在发行两周后迅速攀上日本亚马逊数学类“畅销书第1位”,卖到断货,出版社被迫紧急加印应付市场。

如果你对一个两千多万位的数字没有概念的话,看到这本书的厚度你应该就知道了

出版社的山口和男先生在接受媒体采访时表示,印这样一本书其实并没有什么特别的目的。他还曾考虑将圆周率π印成书,但因为圆周率在小数点以后的位数是无限的,只好作罢。

但2017年年底梅森素数的诞生,再一次促动他把数字印成书的神经,促使他以最快的速度把这本书发行出版。这本书不仅实现了山口和男先生纯粹的愿望,而且这本书的销售过程一不小心成为了出版界的奇闻。


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

对于读者来说,把这本书买回家,精神意义远大于实际意义。自17世纪法国数学家马林·梅森(Marin Mersenne)开始,人们就开始不断寻找梅森素数。找到第50个梅森素数,是数学领域的重大发现,也是人类发展一个新的里程碑。把这个里程碑带回家,这本书更多的是一种信物,代表人类力求不断进步,勇攀高峰的精神。

什么是素数?
为什么一个梅森素数的诞生,引起如此大的轰动?我们先来了解一下什么是素数(prime number)。

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

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

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

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

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

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

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

它们看起来很密集,但随着素数越大,它们之间的距离渐渐变长。重要的是,它们的分布距离是不均等的。要找到一个大的素数,往往需要巨量的计算,要分解和验证它也是这样。为了掌握素数的规律,数学家绞尽脑汁。

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

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

其中,中国数学家张益唐在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世纪法国数学家马林·梅森对它进行了深入研究。为了纪念梅森的贡献,学界把这种数称之为梅森数,如果梅森数为素数,则称之为梅森素数。

在只能手工计算的时代,人们就开始了对梅森素数的寻找,直到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万美元)

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

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

具体的筛法如下:
第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以内的所有素数完全找到。


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

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

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

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

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

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

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环,逆时针13环,这正是费波那契数列当中的数字

欢迎加入本站公开兴趣群
高性能计算群
兴趣范围包括:并行计算,GPU计算,CUDA,MPI,OpenMP等各种流行计算框架,超级计算机,超级计算在气象,军事,航空,汽车设计,科学探索,生物,医药等各个领域里的应用
QQ群:326600878

鲜花

握手

雷人

路过

鸡蛋

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2018-7-23 10:17 , Processed in 0.094391 second(s), 23 queries .