龙空技术网

发现新素数,你也可以丨科学史

中科院之声 5940

前言:

如今我们对“如何生成大素数小数整数”可能比较讲究,各位老铁们都需要知道一些“如何生成大素数小数整数”的相关知识。那么小编同时在网上搜集了一些对于“如何生成大素数小数整数””的相关内容,希望咱们能喜欢,你们一起来学习一下吧!

2018年12月21日,一位名叫帕特里克·罗什的美国人参与“互联网梅森素数大搜索”项目(GIMPS)并成功发现第51个梅森素数282589933-1,它含有24862048个数位。梅森素数是以法国数学家马林·梅森(Marin Mersenne,1588~1648)的名字命名,数百年来人们始终在寻找更大的梅森素数,这究竟是为什么?小G将为你揭晓答案。

GIMPS官网截图

要了解梅森素数,首先要知道什么是素数?早在约公元前300年成书的欧几里得所著希腊数学经典《几何原本》中说(定义VII.11):素数是只能为一个单位所量尽者,即除了1和它本身以外,再无正整数约数的数称为素数(或质数),第1个素数是2,否则为合数。

欧几里得

任何大于1的整数,要么本身是素数,要么可以唯一地写成若干素数乘积,可以说素数是构造整数大厦的砖石。自古希腊时代,寻找素数一直是人们所关注的问题,古希腊数学家埃拉托塞尼(Eratosthenes,约前276~约前195)早已给出著名的“埃拉托塞尼筛选法”。

埃拉托塞尼

若用该法找出100以内所有素数,仿下图画一个10×10的表格,填上1~100. 首先1不是素数,划去;保留素数2,将其所有倍数划去;接着留素数3,将3所有倍数划去,已经被划去的不用管;紧接3后未被划去的是5,保留5并将其倍数划去;紧接5后未被划去的是7,进行同样操作,此时表中未被划去的36个素数为所求。事实上100的平方根10中仅有4个素数,将它们的倍数全部划去即可,该性质可被证明并推广——要筛选出整数n内所有素数,只需将内所有素数的倍数划去。

埃拉托塞尼筛选法

素数分布有一明显特点——随着数值增大,素数越来越少。这很容易解释,较小数字可能因子少,较大数字可能因子多,也就越不可能是素数。1~100中,有36个素数;而10000001~10000100这100个数中,只有2个素数。素数会不会有尽头呢?《原本》(IX.20)中已证明素数无穷无尽。

徐光启与利玛窦合译《几何原本》(1607)首页

认识梅森素数,还需了解“完全数”,《原本》定义(VII.22)相当于:完全数等于其所有真因子之和的数,如6(=1+2+3)是完全数。古希腊人认为完全数代表吉祥,会带来幸福和美好!《原本》(命题IX.36)给出寻找完全数的方法:若是素数,则是完全数。古希腊人在公元1世纪以前就知道前4个完全数——6,28,496和8128,第5个完全数到15世纪才被发现,关键在于寻找形如的素数,这就是梅森素数。

1644年梅森在其所著《物理-数学探索》序言中说:当p=2,3,5,7,13,17,19,31,67,127,257这11个数时,为素数,并证明了前7个数,后面4个数字计算量太大而没有验证,该猜想引起学界极大关注。为纪念他,人们把型的素数称为“梅森素数”,并以记之(其中M是梅森姓氏首字母)。

梅森

此后无数学者都进行过研究,1722年瑞士数学大师欧拉在双目失明的情况下,靠心算证明了为素数;1876年,卢卡斯证明了为素数。1903年,美国数学家科尔在纽约一次数学会议上做了精彩的“无声报告”,他走上讲坛写下:顿时全场响起了经久不息的掌声,不是素数!梅森的猜想有误!1922年,也被验证不是素数!梅森猜想被解决,但人类并没有停止寻找新梅森素数的脚步。

欧拉

虽形式简单,但探究需要高深理论和艰巨计算,至1920年代,人们通过手算艰辛地找到12个梅森素数。计算机的出现,加快了探寻的步伐。1952年,人们将以往的算法编译成计算机程序,在几小时内就找出了5个新梅森素数,自此探寻梅森素数也成为检测计算机性能和相关算法的有效手段。互联网时代产生的分布式计算技术可有效利用互联网空闲计算能力,这使探寻工作如虎添翼,1996年美国数学家沃特曼编写了一个寻找梅森素数程序放在网上供大家免费使用,这就是本文开头的GIMPS项目。1952年至今,计算机共找到39个梅森素数,最新的17个全归功于GIMPS!目前全球有近70万人参加该项目,来吧,你可能就是下一个发现者!

部分梅森素数发现概况

来源:中国科学院自然科学史研究所

温馨提示:近期,微信公众号信息流改版。每个用户可以设置 常读订阅号,这些订阅号将以大卡片的形式展示。因此,如果不想错过“中科院之声”的文章,你一定要进行以下操作:进入“中科院之声”公众号 → 点击右上角的 ··· 菜单 → 选择「设为星标」

标签: #如何生成大素数小数整数 #筛选法判断素数 #筛选法判断素数的依据 #生成大素数算法是什么 #大素数因子