我一个数学家，赚亿点小钱怎么了 022 新的梅森素数

【本章涉及部分数学及算法内容，不感兴趣的可以跳过去】

~

提交梅森素数的流程比较容易。

获得奖励的方式也比较明确。

而决定资金到手时间的则是GIMPS能在多长时间内验证陆洲所提交的数就是新的梅森素数。

如果GIMPS真的要花上很久才验证出来陆洲所提交的数是梅森素数。

那么陆洲所收到相应的奖励也会相应推迟了。

而GIMPS要如何证明陆洲所提交的是梅森素数呢？

首先如何证明一个数是素数？

素数是指大于1的自然数，除了1和它本身之外，没有其他正因数的数。

换句话说，素数只能被1和它自身整除，不能被其他自然数整除。素数的特点是只有两个正因数：1和本身。

而从素数的定义出发的话，就可以通过试除法来验证。

具体来说可以执行下面的操作：

步骤1：选择一个大于1且小于待检查数平方根的数作为除数。如果待检查数为n，则可以选择2到√n之间的数作为除数。

步骤2：将待检查数除以选定的除数。如果除法的余数为0，即待检查数能被选定的除数整除，则待检查数不是素数。

步骤3：如果待检查数不能被选定的除数整除，继续增加除数的值，重复步骤2。

步骤4：如果在2到√n之间没有找到能整除待检查数的除数，则待检查数是素数。

不可否认，试除法简单粗暴，但这仅仅限于所要你所要验证的数并不大的时候。

但当问题变成如何证明一个超大的数（这个数有上千万位）是素数的时候，再继续用试除法就显得很呆。

这里面主要涉及到计算复杂度的问题。

（计算复杂度听起来是一个计算机方面的问题。

但正如前面说得那样，现代数学和计算机科学之间的关系早已就是你中有我，我中有你。

就算是搞数学的，但凡是涉及到利用计算机作为工具来解决问题的时候就不得不考虑周全。

很多经典的数学问题其本质上也是计算机问题。

比如说七个数学千禧难题之一的P/NP问题就既是数学问题，同时也是计算机问题。

更具体来说，其本质是计算复杂度的问题。

P指的是可多项式时间内解决的问题，而NP是指可多项式时间内验证解的问题。

P/NP问题是计算复杂度理论中的重要问题。它们涉及了算法是否存在有效的解决方法以及在何种时间内可以解决问题的核心问题。

P问题指的是那些可以在多项式时间内解决的问题，即存在一个多项式时间复杂度的算法可以解决这些问题。这些问题的解决方法相对较高效，计算复杂度可控，例如线性时间复杂度、对数时间复杂度等。

NP问题指的是那些可以在多项式时间内验证解的问题，即如果有一个解，可以在多项式时间内验证该解的正确性。然而，尚未找到多项式时间复杂度的算法来解决这些问题，因此它们被认为是比较困难的问题。

听起来P和NP有些容易混淆？

确实如此，因为P问题本身就是NP问题的子集，即所有的P问题也是NP问题。

但目前尚不清楚P问题和NP问题之间是否存在严格的相等关系，即P=NP还是P≠NP。

这是著名的PvsNP问题，它是计算机科学领域中最重要的未解决问题之一。

解决PvsNP问题将对计算复杂度理论和算法设计产生重大影响。

如果P=NP成立，那么意味着存在多项式时间复杂度的算法来解决所有NP问题，从而具有广泛的实际应用；

而如果P≠NP成立，那么NP问题在计算上将更加困难，需要使用更加高效的算法和技术来求解……）

-

而说到算法复杂度本身，计算复杂度是衡量算法执行时间或空间需求的度量标准。

它描述了算法运行时间或空间使用量随输入规模增加时的增长速度。

计算复杂度是对算法效率的一种度量，可以帮助我们比较不同算法之间的效率，并选择最适合特定问题的算法。

常见的计算复杂度包括时间复杂度和空间复杂度。

时间复杂度是描述算法执行所需的时间量。

它通常用大O符号表示，表示算法执行时间随着输入规模增长的上界。时间复杂度可分为以下常见类别：

常数时间复杂度：O(1)，算法的执行时间与输入规模无关。

线性时间复杂度：O(n)，算法的执行时间与输入规模成正比。

对数时间复杂度：O(logn)，算法的执行时间随输入规模的增加而增加，但增长速率较慢。

平方时间复杂度：O(n2)，算法的执行时间与输入规模的平方成正比。

指数时间复杂度：O(2^n)，算法的执行时间随输入规模呈指数级增长。

更高阶复杂度如O(n!)（ps：多项式复杂度）和O(n^n)（ps：指数复杂度）等。

而空间复杂度是描述算法执行所需的额外空间或内存量。

类似于时间复杂度，它也用大O符号表示，表示算法所需的额外空间随着输入规模增长的上界。

理解计算复杂度的重要性在于能够评估和比较不同算法之间的效率，以选择最适合解决问题的算法。

通常情况下，我们希望选择时间复杂度低且空间复杂度较小的算法，以实现更高效的计算和资源利用。

计算复杂度还可以指导算法设计和优化，以提高算法的性能和效率。

而从计算复杂度的角度来说，试除法是一种简单但相对较慢的素数验证方法。

因为试除法需要逐个检查每个可能的除数，当待检查数非常大时，该过程变得非常耗时。

试除法的时间复杂度随待检查数的大小呈指数增长，亦即其时间复杂度是指数级的。

通过试除法来验证素数，不要说是对付上千万位的数，就算是对付一些超大数，试除法也只会很乏力。

对于超大规模的素数，实际应用中是不适用应用试除法验证如此大的数是否为素数。

实际应用中，对于超大规模的数，如果要验证其是不是素数一般都采用别的更高效的方式。

至少该方式所对应的复杂度也不能是指数复杂度。

指数复杂度通常意味着问题的解决时间会随着问题规模的增长呈指数级增长。

这并不一定意味着问题无解，而是指在实际计算上，对于较大规模的问题，找到解决方案所需的计算资源和时间可能是不可行的。

对于某些问题，尽管其具有指数复杂度，但仍然存在有效的解决方案。

例如，某些组合优化问题，如旅行商问题（TSP），在理论上是指数难解的，但有许多启发式算法和近似算法可以在实践中找到接近最优解的解决方案。

然而，对于某些问题，指数复杂度可能意味着找到精确解决方案是困难的或不切实际的。

例如，对于某些特定的组合优化问题，如子集和问题（SubsetSum），由于其指数复杂度，当问题规模较大时，无法通过穷举搜索所有可能的解决方案来找到最优解。

因此，指数复杂度并不直接表示问题无解，而是指在实际情况下，对于大规模问题找到精确解决方案可能非常困难。

而如果要验证一个超大数是素数除了试除法之外，还有很多别的方式。

譬如说证明一个超大数是素数的方法可以使用Miller-Rabin素数测试。

Miller-Rabin素数测试是一种概率性测试，可以高概率确定一个数是否为素数。

以下是使用Miller-Rabin素数测试证明一个超大数是素数的一般步骤：

选择一个适当的测试次数（通常是几十到几百次），记为k。

将待检查的超大数减1，得到数n-1。

将n-1分解为d*2^s的形式，其中d是奇数，s是非负整数。即n-1=d*(2^s)。

对于每个测试次数，选择一个随机整数a，满足1an-1

计算a^dmodn，并检查结果是否为1或n-1。

如果结果是1或n-1，则进行下一次测试。

如果结果不是1且不是n-1，则进行s-1次迭代计算：计算(a^d)^2modn，依次重复。

如果在k次测试中的任何一次迭代中得到的结果不是1且不是n-1，则n不是素数。

如果在k次测试中所有迭代中都得到的结果都是1或n-1，则n很可能是素数。

需要注意的是，由于Miller-Rabin素数测试是概率性的，有一定的错误概率。

但是，通过增加测试次数k，可以将错误概率降低到非常小的程度。

这个过程听起来要比试除法繁琐很多。

但从计算复杂度的角度来出发，Miller-Rabin素数测试的时间复杂度是多项式复杂度。

具体而言，它的时间复杂度为O(k*log?(n)*(log?(n))3)，其中k是测试次数，n是待检查的超大数。

在Miller-Rabin素数测试中，迭代次数是由测试次数k决定的。

每次迭代的计算包括取模运算和幂运算，它们的复杂度都是多项式级别的。

与指数复杂度的算法相比，多项式复杂度的算法在处理超大数时更加高效。

尽管Miller-Rabin素数测试是一种概率性测试，但随着测试次数的增加，错误概率可以降低到极小的程度。

虽然Miller-Rabin素数测试具有多项式时间复杂度，但如果是对于比超大数还要大的数（也就是是说对于一些动辄千万位的数非常大的数），想要验证其是不是素数仍然需要相当大的计算资源和时间才能完成测试。

甚至于在实际应用中，常常会结合其他优化技术和算法来提高素数测试的效率。

而如何验证一个数是不是梅森素数呢？

首先梅森素数也是素数的一种。

因此要先判定这个数是素数。

而后再验证这个数是否符合梅森素数的定义。

具体来说，可以依靠Lucas-Lehmer测试即卢卡斯-莱默检验法。

卢卡斯-莱默检验法（Lucas-Lehmertest）是一种用于验证梅森素数的特定形式的素数测试方法。

它仅适用于梅森素数的验证（形如2^p-1的素数，其中p是一个素数。）

卢卡斯-莱默检验法的原理如下：

初始化s=4。

重复进行以下步骤p-2次：计算s的平方减去2，并将结果对2^p-1取模，即s=(s^2-2)%(2^p-1)。

如果最终得到的s等于0，则该数2^p-1是素数；否则，它不是素数。

卢卡斯-莱默检验法是一种确定性的测试方法，可以准确判断形如2^p-1的数是否为素数。

需要注意的是，卢卡斯-莱默检验法只适用于特定形式的梅森素数，即形如2^p-1的素数。

尽管该算法对于这类素数非常高效，但并不适用于一般的素数验证。对于一般的素数，其他素数测试算法如Miller-Rabin素数测试更为常用和有效。

该算法的时间复杂度为O(p^2)，其中p是待验证的素数。

按照这个说法来说，如果陆洲提交了“2的74，207，281次方-1是梅森素数”这个结论之后。

为了对这个结论进行验证，74，207，281是输入规模（或问题的大小），那么执行该算法的时间将取决于该数的平方。

即相应的算法时间复杂度为O(74，207，281^2))=O(5，503，401，983，592，961)。

需要注意的是，时间复杂度仅提供了算法执行时间增长的大致趋势和量级估计，并不能直接转化为具体的执行时间。

实际的执行时间还受到多种因素的影响，包括计算机硬件、算法实现的优化程度、输入数据的特征等。

因此，对于如此大的输入规模，具体的执行时间将取决于实际执行环境和算法的实现细节。

一般来说，对于O(5，503，401，983，592，961)这种时间复杂度的问题并不是所有的计算资源和现有计算机系统都能驾驭如此棘手的问题。

不过对于应用了分布式计算的GIMPS项目应该是问题不大的。

即便是有一点小问题，这也不是陆洲所关心的。

陆洲要做的只是将“2的**次方-1是梅森素数”这个结论进行程序化的提交就完事了。

至于具体如何验证这工作倒是跟陆洲关系不大。

虽然具体如何验证之类的内容跟陆洲关系不大，但陆洲却不能无视这些。

即便是很多平平无奇的成果甚至是很多云淡风轻般得出的学术进步也不是一蹴而就达成的。

一点点微小的成果的出现其背后所历经的艰辛是难以想象的。

这可能需要动用庞大的人力资源甚至是计算资源。

一个平平无奇的项目背后往往有着无数搬砖的人在默默付出。

只看到一门学科华丽的外表却看不到背后的各种艰辛是不应该的。

-

陆洲没怎么费力就完成了GIMPS中相应的账号的注册。

并且完成了“2的74，207，281次方-1是梅森素数”这个结论提交。

不过饶是如此，事情也并没有结束，怎样让自己提交的这个结论被注意到呢？

毕竟每天GIMPS中要处理的数据是相当庞大的。

不过这些似乎这不重要了，因为陆洲发现随着其完成了“2的74，207，281次方-1是梅森素数”这个结论提交。

沉寂的系统居然有了新的反应。

端午读书！充100赠500VIP点券！ 立即抢充(活动时间：6月8日到6月10日)