一名程序员意外发现迄今最大素数,长约25000000位!

作者 : 开心源码 本文共3308个字,预计阅读时间需要9分钟 发布时间: 2022-05-14 共296人阅读

2^82,589,933-1!

这个有着大约 2500 万位的数字,正是迄今为止人类发现的最大的素数。

最近,一位来自美国佛罗里达州的程序员 Patrick Laroche,利用互联网梅森素数大搜索项目(GIMPS),成功发现该素数,它有 24862048 位数字,这也是人类发现的第 51 个梅森素数,名为 M82589933。 Patrick Laroche也因而取得了 3000 美元的奖金。

假如有想要学习C/C++的小伙伴,可以关注小编【C/C++企鹅群496926338】,wx公众号:CPP_cx 小编也有5年编程经验了,免费送一套比较系统的资料、教程和工作经验,就当是福利吧!加QQ群:496926338

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

在这次发现之前,第 50 位梅森素数可谓出尽风头,2018 年 1 月 13 日,日本一家出版社为第 50 位梅森素数做了一本书,据报道 4 天就卖出了 1500 本,发行两周后迅速攀上日本亚马逊数学类“畅销书第1位”。

图 | 最大素数局部展现(来源:QUARTZ)

而在这一次的发现中,主人公?Patrick Laroche 并不是专门研究数学的数学研究者;其次,GIMPS 这个项目并不仅仅是数学工作者可以使用,而是所有人都能使用的一个数学工具。

20 世纪 90 年代中后期,在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下,建立了世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜索(GIMPS)。人们只需在 GIMPS 的主页上下载一个计算梅森素数的免费程序,即可以立即参与该项目来搜寻新的梅森素数。Patrick Laroche 就是尝试使用 GIMPS 的千万个志愿者的一员。

要知道,人类曾经寻觅这类素数的方式非常简单粗暴但是收获颇少。

例如 100 以内的素数,最简单的方法就是“试”——将 100 个数字写出来,一个个去质因数分解,不能分解的就是素数。图中,黄色标出的就是素数,100 以内的素数共有 25 个。这样的操作,首先我们要把所有的数都写出来,而后逐个辨别,找 100 以内的素数还不算很麻烦,但是 1000、10000 之后呢?这样的方法就不实用了。

那么我们可以用另一种方法——“筛法”,简单来说就是将 100 以内的数一遍一遍挑选,剩下来的就是我们想要的素数。首先,将 100 以内 2 的倍数去掉,而后 3 的倍数去掉,接着 5 的倍数、7 的倍数去掉,以此类推。筛到最后,就只剩下了我们的 25 个素数。这种“筛法”相对来说比较简单,由古希腊的哲学家埃拉托斯特尼初次提出,他也是第一个丈量地球的人,十分天才。

假如有想要学习C/C++的小伙伴,可以关注小编【C/C++企鹅群496926338】,wx公众号:CPP_cx 小编也有5年编程经验了,免费送一套比较系统的资料、教程和工作经验,就当是福利吧!加QQ群:496926338

在找出素数之后,数学家又在想,能不能有一种方式能处理所有素数的分布或者者素数的计算公式呢?

这就要提到几个著名的猜想了:“哥德巴赫猜想”、“孪生素数”、还有今年受到热议的“黎曼猜想”。这些著名猜想都对素数的分布提出了阐述,但是至今还未完全被证实。

数学家退而求其次,能不能找到一个公式,并证实通过这个公式算出来的数肯定是素数呢?这就是著名的“梅森素数”。

假如有想要学习C/C++的小伙伴,可以关注小编【C/C++企鹅群496926338】,wx公众号:CPP_cx 小编也有5年编程经验了,免费送一套比较系统的资料、教程和工作经验,就当是福利吧!加QQ群:496926338

图|法国数学家马林·梅森(Marin Mersenne , 1588-1648)

最早开始研究梅森素数的是古希腊数学家欧几里得。他早在公元前 300 多年,就开创了研究梅森素数的先河。在他的名著《几何本来》第九章数论中,就提到了梅森素数以及完全数的概念。

在这之后,17 世纪的法国数学家马林·梅森(Marin Mersenne)开始研究梅森素数,在欧几里得、费马等人有关研究的基础上对梅森素数做了大量的计算和验证。

“梅森素数”是这样一类数,由?Mp=2p-1 这个公式确定。当 p 为合数时,Mp肯定为合数. 但当 p 为素数时,Mp不肯定皆为素数,例如最小的梅森素数是M2=22-1=4-1=3, 但是 M11=211-1=2047=23*89 就不是素数。

梅森于 1644 年在他的《物理数学随感》一书中归纳了 M2 到 M257 之间的所有梅森素数。尽管有所纰漏(M67 和 M257 都不是素数),但是这是在那个只有烂笔头和好记性的年代,将这些庞大的数字,例如 2257-1 算出来并验证能否是素数真的是一项庞大的工程。

为了纪念梅森的贡献,梅森素数也因他得名。梅森素数提供了一种寻觅素数的“捷径”,所以如今人们发现的已知最大素数几乎都是梅森素数,因而寻觅新的梅森素数的历程也就几乎等同于寻觅新的最大素数的历程。

随着时间的推进,计算机也出现了,寻觅梅森素数也进入了“计算机时代”。

超级计算机以及相应素数算法的出现加快了我们寻觅梅森素数的速度,例如美国数学家鲁滨逊(1911~1995)在莱默指导下将此方法编译成计算机程序,使用 SWAC 型计算机在几个月内就找到了 5 个梅森素数:M521 、M607 、M1279 、M2203 和 M2281。

但使用超级计算机寻觅梅森素数实在太昂贵了,而且可以参加的人也有限,寻觅素数变成了世界上极少数人的游戏。

随着网络的出现,梅森素数得以“飞入寻常百姓家”,GIMPS 的出现标志着寻觅梅森素数进入了“网络共享时代”。从 1996 年投入使用开始,GIMPS 已经帮助我们发现了 17 个梅森素数了(第 35 个到第 51 个)。

但是,梅森素数又有什么用呢?

说了这么久,梅森素数不就只是一种素数么?与我们的日常生活有什么联络么?

首先,梅森素数自古以来就是数论研究的一项重要内容,历史上有不少大数学家都专门研究过这种特殊形式的素数。梅森素数还是数学中一种完美的表现,我们可以将梅森素数做这样一个运算:

其中 n 就是一个完全数,即它的所有真因数相加之和等于它本身。例如 n=6 就是一个完全数,6=1x2x3=1+2+3。它是由 M2通过上面的公式得到,其实得到一个梅森素数也就得到了一个完全数。

其次,寻觅梅森素数是目前发现已知最大素数的最有效途径。自欧拉证实 M31 为当时最大的素数以来,梅森素数基本领跑最大素数榜。更多的是,寻觅梅森素数是测试计算机运算速度及其余功能的有力手段,如 M1257787 就是 1996 年 9 月美国克雷公司在测试其最新超级计算机的运算速度时得到的。

计算、发现和验证梅森素数能对计算机性能的评级和改进都是有独特作用的,由于研究梅森素数的过程中会牵涉到冗长的大数计算,这是表现计算机性能的一个重要的指标,随着梅森素数越来越大,计算量剧增,这就要求计算方法和计算技术的创新。

谈及实际应用的意义,梅森素数能应用于现代密码学中。

我们十分熟习的银行加密系统,几乎天天都会用到,如今比较流行的加密算法是由 MIT 三位科学家开发的非对称加密算法(RSA 算法),这种算法是基于数学运算原理加密的,在加密解密过程中需要用到素数相关的计算,例如质因数分解等。而素数作为加密解密的核心是安全性的标志,一旦这个素数很容易被找到也就代表这个加密算法安全性很差,大素数的应用将大大加强算法的安全性。

寻觅梅森素数已经从“手算时代”、历经“计算机时代”到了我们的“网络共享时代”。计算机的作用毋庸赘述,而 GIMPS 这种互联网共享模式也得到了成功的验证,它成功地让非数学专业或者者非数学研究的人都参加到了数学研究中来,虽然他们中很多人使用这个软件的初衷并不是参加数学研究,例如 Patrick Laroche 发现 282589933-1 之前,曾用 GIMPS 的软件测试自己的电脑。GIMPS 将他们的闲散资源、闲散时间以及闲散“思维”都集中了起来,这是一种模式上的创新。

假如有想要学习C/C++的小伙伴,可以关注小编【C/C++企鹅群496926338】,wx公众号:CPP_cx 小编也有5年编程经验了,免费送一套比较系统的资料、教程和工作经验,就当是福利吧!加QQ群:496926338

新的一年即将来临,让我们期待长度更加可观的的梅森素数被发现吧

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 一名程序员意外发现迄今最大素数,长约25000000位!

发表回复