酷应用

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

百家作者：DeepTech深科技 2018-12-27 12:37:25

点击上图小程序，参与全球新兴科技峰会

2^{825，899，33}-1！

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

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

图丨迄今最大素数（来源：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 个素数。这种“筛法”相对来说比较简单，由古希腊的哲学家埃拉托斯特尼首次提出，他也是第一个丈量地球的人，十分天才。

在找出素数之后，数学家又在想，能不能有一种方式能解决所有素数的分布或者素数的计算公式呢？

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

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

图|法国数学家马林·梅森（Marin Mersenne , 1588－1648）

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

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

“梅森素数”是这样一类数，由 M_p=2^p-1 这个公式确定。当 p 为合数时，M_p一定为合数. 但当 p 为素数时，M_p不一定皆为素数，例如最小的梅森素数是M₂=2²-1=4-1=3, 但是 M₁₁=2¹¹-1=2047=23*89 就不是素数。

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

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

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

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

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

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

但是，梅森素数又有什么用呢？

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

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

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

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

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

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

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

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

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

-End-

在科技发展越来越超乎普通人想象的年代，我们迫切地需要一场巅峰对话来总结过去，指引未来。2019 年 1 月 19 - 21 日，EmTech China 全球新兴科技峰会，超过 30 位全球科技“掌舵人”将亲临北京，为你展开前沿技术的壮丽蓝图，为你解读技术背后的未来价值！