狩猎14载终于发现最大已知素数,它有这么长!

数学上,将形如2^n-1的数称为“梅森数”(Mersenne numbers)。如果这个数还是个素数,那我们就说它是“梅森素数”(Mersenne Prime)。17世纪,法国数学家梅森列出了n小于257的所有梅森素数。尽管其中包含了几项错误值,但人们还是肯定了他的成就并将这样的数正式命名为梅森数。

梅森素数的分布极不规则。寻找梅森素数不仅需要高深的理论、纯熟的技巧,还需要进行艰巨的计算。有时许多年不能找到一个,有时能一下找到好几个。而探索梅森素数的分布规律比寻找新的梅森素数更为困难。

1996年1月,美国数学家及程序设计师乔治·沃特曼(George Woltman)编写了一个梅森素数计算程序。他把程序放在网页上供数学家和数学爱好者免费使用,这就是最初的互联网梅森素数大搜索(Great Internet Mersenne Prime Search,GIMPS)。任何拥有个人电脑的人都可以加入GIMPS,成为一名素数猎人。 从1997年至今,所有新的梅森素数都是通过GIMPS分布式计算项目发现的。

在2018年1月3日,GIMPS发现了已知的最大素数。这是第50个梅森素数。新的素数2^77232917-1,也被称为M77232917,共有23249425位。它比上一个记录的素数大了近一百万位数,大到可以写满9000页纸。如果你每秒写五位数,占一英寸长(2.54厘米),那么54天之后,你会有一个超过118公里——比以前的素数记录还要长5公里——的数字。

该素数的发现者乔纳森·佩斯(Jonathan Pace)是使用免费GIMPS软件的数千名志愿者之一,用GIMPS狩猎素数长达14年。乔纳森是美国田纳西州一名51岁的电气工程师。2017年12月26日起,他的一台配备英特尔i5-6600 CPU的计算机开始了六天不间断运算。为了证明在素数发现过程中没有错误,新的素数又在四种不同硬件配置的设备上使用四个不同的程序进行独立验证:亚伦·布劳瑟(Aaron Blosser)于37小时内在Intel Xeon服务器上使用Prime95进行了验证;大卫·斯坦菲尔(David Stanfill)于34小时内在AMD RX Vega 64 GPU上使用gpuOwL进行了验证;安德里亚斯·霍伦德(Andreas Höglund)于73小时内使用NVidia Titan Black GPU上的CUDALucas进行了验证;恩斯特·梅尔(Ernst Mayer)还在82小时内在32核Xeon服务器上使用他自己的程序Mlucas进行了验证;另外,安德里亚斯·霍伦德也在65小时内使用在Amazon AWS上运行的Mlucas完成了确认。

自梅森素数命名300年来,数学研究者一直不断探索着它的相关性质。目前这个新的大素数的实际用途很少,以至于有人问:“为什么要寻找这些大素数”

在20世纪90年代早期,苹果杰出科学家理查德·克兰德尔(Richard Crandall)发现了一种大乘数的运算方法,它可以使卷积速度加倍。这种方法不仅适用于素数搜索,而且适用于其他领域的计算工作。在这项工作中,他获得了苹果计算机公司拥有的快速椭圆加密系统的专利,梅森素数在该系统中用于快速加密和解密信息。 

而乔治·沃特曼用汇编语言实现了克兰德尔的算法,从而实现了一个前所未有的高效素数搜索程序。这个工作促成了GIMPS项目的建立与发展。 

梅森素数还可以应用在密码学。现在人们已将大素数用于现代密码设计领域,其原理是:将一个很大的数分解成若干素数的乘积非常困难,但将几个素数相乘却相对容易得多。在这种密码设计中,需要使用较大的素数。素数越大,密码被破译的可能性就越小。对梅森素数的探究促进了计算技术、程序设计技术和计算机检测技术的发展,还推动了快速傅立叶变换的应用。

此次发现将为乔纳森带来3000美元的GIMPS研究发现奖奖金。电子前沿基金会(Electronic Frontier Foundation)将向最先发现一亿位素数的人提供150,000美元的奖金。任何有志于搜索梅森素数的人都可以去www.mersenne.org/download/ 下载软件。(编辑:vicko238)

题图来源:Dan Hogan/ScienceDaily

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *