已知的最大素数:简史

最大的已知素质今天是24,862,048位Mersenne.主要的282589933.-1在2018年12月发现,但历史上有多大的是“最大的已知素数”?从历史上看,如何找到这些素数?我们将简要讨论以下每个问题。

[向上]内容

  1. 在电子计算机
  2. 电子电脑的年龄
    • 年度最佳记录
    • 桌子年度最佳记录
  3. 后记:没有更多的预测

[向上]第一部分:在电子的电脑

关于法国和尚马林·梅森的第一猜想及其错误的信息,看到这个链接

许多早期的作家(错误地)认为如果p是质数,那么M也是p= 2p1。这些数字,现在被称为Mersenne号码,是早期大部分大素数搜索的重点。这些数字的早期历史充斥着许多关于原始性的错误主张,甚至像梅森、莱布尼茨和欧拉这样的著名人物也是如此。所以我们对我们的第一位记录保持者表示怀疑:

到1588年,Pietro Cataldi已经正确地证实了217.-1 = 131071和219.-1 = 524287均为素数[Cataldi1603.]。

但是卡特迪也说错了2n23 29 31 37中的每一个都是质数-1。这很有趣,因为Cataldi的发现是通过构建Shanks所说的“第一个广延质数表——750以内”[shanks78,p14]。这些表格足以显示219.-1是素数(其平方根约为724)但是不是大到足以处理这四个更大的数字!

注意:一些作家(例如,[Picutti1989]和[BS96.包括质数8191=213.-1(1458年前,Codice Palatino 573)和131071=217.-1(1460,Codex OTTB。Lat 3307)在他们的记录列表中。但我们缺乏他们缺乏证据表明他们当时被证明是普遍的猜测,而不是幸运的猜测。

1640年,费姆表明如果p是一个奇数的素数,然后是2的所有主要二数p-1有表格2kp+1。然后,他迅速显示了23(有因素47有因素k= 1)和37(因子223k= 3)。最后,在1738年,欧拉通过求出233这个除数证明了卡特迪对29的估计也是错误的。这里,利用费马的结果,k= 4。这只是用Fermat结果尝试的第二个数字k= 2,k= 3屈服复合材料(所以我会猜测费玛也知道这个因素)。请注意,Cataldi自己的素质表中发现的小因素显示了Cataldi的错误,并且没有超过两种试验部门!

欧拉为我们提供了第一个清晰的记录(也许除了日期),他证明了卡特迪在31岁时是正确的:

到1772年欧拉使用了聪明的推理和试验司来显示231.-1 = 2147483647是素数。

当Euler发给Goldbach的歌手时,实际日期必须在1752年10月28日之间[文本欧拉档案说他对这个数字不确定(尽管他之前把它列为素数),1772年,一个字母[文本]从欧拉发表给伯努利,说他证明了231.-1通过显示2的所有主要二级的素数31.-1必须有两个表格中的一个248n+1和248.n+63,然后除以所有小于46339的质数[Dickson19,pp18-19]。这需要一个简单的定理哪个比上面的Fermat的结果强。(欧拉已列出231.-1是一个质数,早在1732年,他和2一起做了这个实验41.1和247.-1两者都是复合材料[翻译]。)

注意:一些作家(例如,[BS96.,P309])包括“通过LOOFF”的PRIMES 9999999000001(1851)和他们的表中的67280421310721(1855年1月1日1855年1月1日)。第一个出现在一个带有问号的洛杉矶表中,但reuschle [Reuschle1856.,pp.3,18]索赔Looff已证明它是素数。Thomas Clausen提供了分解274177·67280421310721的264.在1855年1月1日写给高斯的一封信中,提到两个因子都是质数[Biermann1964]。但它仍然是一种没有方法的主张。

到1867年,兰德里发现了一个更大的素数,仍然是审判司,占2倍59.-1(即(259.-1)/ 179951 = 3203431780337),这一原稿持续了比任何其他更长的记录-梅森会(在他的发现之前或之后)。然而,所有这些努力都被一项新的数学发现掩盖了,所以我们暂停一下,来总结一下现代计算机出现之前的所有质数记录(我知道的)。(从长远来看,我们能找到多大的质数总是由数学决定的。)

表1.电子计算机前的记录
数量 数字 一年 箴言
方法
217.-1 6 1588 Cataldi. 试除法
219.-1 6 1588 Cataldi. 试除法
231.-1 10. 1772 欧莱尔 试验部++
(259.1) / 179951 13. 1867年 兰德里 试验部++
2127.-1 39. 1876年 卢卡斯 卢卡斯序列
(2148.+ 1) / 17 44. 1951. Ferrier. Proth定理

到1876年,卢卡斯发明了一种聪明的检验方法来确定梅森数是否是质数。他的方法是Lehmer甚至更简单在20世纪30年代,仍然用于发现记录素数!

1876年,卢卡斯证明了2127.-1 = 170141183460469231731687303715884105727是素数。

“直到1951年,这仍然是已知的最大素数”[HW79这个记录维持了75年,可能会作为发现的最大质数而永远保持下去通过手动计算

1951年,费里尔使用了一台机械台式计算器和基于费马小定理的部分逆的技术寻找并证明质数),通过找到一个44位的质数来稍微改善这个记录:

1951年,Ferrier发现了素数(2148.+ 1) / 17 = 20988936657440586486151264256610222593863921。

通过此记录,我们结束了电子计算机前的时期,因为在同一年中,通过计算机设置了79位数字的新记录。

注:很难把费瑞厄的发现按时间顺序放在米勒&惠勒的作品中。我们遵循传统的顺序,把费瑞厄的放在第一位,但是我们有充分的理由怀疑这一点

有关更多信息,请参见数字理论的历史伦纳德·迪克森[Dickson19]。

[向上]第二部分:年龄电子计算机

1951年,米勒和惠勒通过找到几次素质开始电子计算年龄:

k 127.+ 1k= 114,124,388,408,498,696,738,774,780,934和978

除了79位的新纪录外:

180(M.127.)2+ 1 (M127.= 2127.1) (MW51.]。

这一记录很快就被Raphael Robinson在第二年使用SWAC(标准西部自动计算机)发现的5个新的Mersennes所取代。这是罗宾逊编写的第一个程序,而且在他第一次尝试时就运行了!不仅如此,他的程序当天还发现了两个新的质数记录!他写道[罗宾逊54.]:

该计划于1月30日在SWAC上首次试验,当天发现了两个新的质数[M521,米607, 6月25日又发现了另外三个质数1279[M2203]和10月9日[m2281]。
[令人惊讶的日志(数字)与年份的线性图形]

有趣的是1949年的拓扑学家纽曼使用原型曼彻斯特电子计算机(具有1024位存储),首先尝试通过计算机找到Mersenne Primes。也许是因为艾伦图灵纽曼从1948年到1950年在这台机器上工作,并改进了纽曼的程序,这是第一次尝试用(电子)计算机寻找质数,有时被认为是他的功劳(例如,[罗宾逊54.]和[Ribenboim95p93])。优秀的艾伦图灵互联网剪贴簿有这台机器的照片。

我们将米勒、惠勒和罗宾逊的记录作为下图的第一个点——注意垂直刻度!

在接下来的几年里,进步就像计算机速度的增长一样稳定。Riesel发现米3217使用瑞典BESK机;赫维茨发现米4253和M.4423使用IBM 7090(见下一段);吉利斯用ILLIAC-2找到了M9689,米9941和M.11213。Tuckerman发现了M.19937使用IBM360。

令人惊讶的是,赫维茨知道M4423秒之前米4253(因为输出的堆叠方式)。约翰·塞尔弗里奇(John Selfridge)问道:“机器的结果在被‘发现’之前需要由人类观察吗?”赫维茨回答说:“先不考虑计算机是否知道,如果把输出堆起来的计算机操作员看了会怎么样?”在下表中,我断定Hurwitz是在读取输出时发现了质数的,所以M4253永远不是最大的已知素数。

表2。电子电脑记录
数量 数字 一年 箴言
180(M.127.)2+ 1 79. 1951. EDSAC1 米勒和惠勒
521 157. 1952年 Swac. 罗宾逊(1月30)
607 183. 1952年 Swac. 罗宾逊(1月30)
1279 386. 1952年 Swac. 罗宾逊(6月25日)
2203 664 1952年 Swac. 罗宾逊(10月7日)
2281 687. 1952年 Swac. 罗宾逊(10月9日)
3217 969 1957年 伯克 Riesel
4423 1,332 1961年 IBM7090. 赫尔维茨
9689 2917年 1963年 ILLIAC 2 Gillies
9941 2,993 1963年 ILLIAC 2 Gillies
11213 3376年 1963年 ILLIAC 2 Gillies
19937 6002年 1971. IBM360 / 91. 塔克曼
21701. 6,533 1978年 疾病预防控制中心网络174 &
23209 6987年 1979年 疾病预防控制中心网络174
44497 13,395 1979年 克雷1 纳尔逊&Sloctinski.
86243 25,962 1982年 克雷1 Sloctinski.
132049 39,751. 1983年 克雷X-MP Sloctinski.
216091 65050年 1985年 克雷X-MP / 24 Sloctinski.
391581·2216193-1 65,087 1989年 Amdahl 1200. 阿姆达6
756839 227,832 1992年 Cray-2 Sloctinski.&等等。(笔记)
859433. 258,716. 1994年 CRAY C90. Slocisski&gage
1257787 378,632 1996年 克雷T94 Slocisski&gage
1398269 420,921 1996年 奔腾(90 MHz) armengaud.,狼人等等。[吉普斯]
2976221 895,932 1997年 奔腾(100 Mhz) 斯宾塞,狼人等等。[吉普斯]
3021377. 909526年 1998年 奔腾(200 MHz) 克拉克森,狼人,kurowski.等等。[吉普斯,PrimeNet]
6972593 2,098,960 1999年 奔腾(350 MHz) Hajratwala,Woltman,Kurowski等。[Gimps,Primenet]
13466917 4,053,946 2001 AMD T-Bird (800mhz) 卡梅隆,Woltman,Kurowski等。[Gimps,Primenet]
20996011 6320430年 2003 奔腾(2 GHz) 沙佛,Woltman,Kurowski等。[Gimps,Primenet]
24036583 7235733年 2004 奔腾4 (2.4 ghz) Findley.,Woltman,Kurowski等。[Gimps,Primenet]
25964951 7,816,230 2005 奔腾4 (2.4 ghz) 诺瓦克,Woltman,Kurowski等。[Gimps,Primenet]
30402457 9,152,052 2005 奔腾4 (2GHz升级至3GHz) 库珀,布恩,Woltman,Kurowski等。[Gimps,Primenet]
32582657 9808358年 2006 奔腾4 (3ghz) Cooper, Boone, Woltman, Kurowski等人[GIMPS, PrimeNet]
43112609. 12978189年 2008 英特尔核心2 Duo E6600 CPU(2.4 GHz) E_Smith,Woltman,Kurowski等。[Gimps,Primenet]
57885161 17425170年 2013 英特尔Core2 Duo E8400(3 GHz) Cooper, Woltman, Kurowski等人[GIMPS, PrimeNet]
74207281. 22,338,618 2016 英特尔i7 - 4790 CPU Cooper, Woltman, Kurowski, blossom等人[GIMPS, PrimeNet]
77232917 23249425年 2018 英特尔I5-6600 CPU. PACE,Woltman,Kurowski,Blosser等人。[Gimps,Primenet]
82589933. 24862048年 2018 英特尔I5-4590T CPU. Laroche, Woltman, bloser等[GIMPS, PrimeNet]

好奇地是素数74207281.在被人类发现前几个月就被机器发现了,看到了吗新闻稿为了这个素质。

[日志(数字)的半线性图与年份]

所有的梅森档案都是用Lucas-Lehmer测试另外两个人使用Proth定理(或类似的结果)。的阿姆达6J布朗,C诺尔,B Parady,G Smith.,J。史密斯年代Zarantonello

[向上]结婚:没有预测

什么时候会有一个10亿的质数?好问题!在GIMPS搜索的早期,我的预测是合理的,但最近事情已经轮到了(参见图表)使用简单回归和过去的历史缺乏预测的图表。我的最后预测是脱离了!

我不想再做时间预测了。所以我们将以一个线性图和下面的一个不必要的立方结束。有用的未来预测不应该仅仅基于页面上的启发式下一个Mersenne在哪里?,还应该跟踪GIMPS等项目的使用数据。是现在的参与者,而不是过去的参与者,将找到下一个质数。

图
从Primepages ©Chris Caldwell。