【文末赠书】价值百万大奖的幸运质数

2019 年 9 月 7 日 算法与数学之美

●◆●◆●

真实世界的复杂性使得获取对它透彻且直接的认知，不能说是不可能，但也是非常艰难的。所以一直以来，世界的征服者秉持“分而治之”的原则，试图减小难度或是对其进行分层。例如柏拉图在对话录《斐多篇》中提及： “人必须理解思想在由显著的多样性向统一知识转变的过程中所起的作用。 ”

在一个逐渐简化和提炼的过程中，真实的描述首先被缩减为概念和表意文字，然后是文字、字母这些构成了一套能够代表语言的整体复杂性，而非思想的整体复杂性的工具。虽然字母的数量局限在几十个，但这并不影响它们通过互相结合产生无限词汇的潜力。

但似乎对于万物而言，不论是其表征还是其物理实际，都能上溯至一个有限量的词库，在那里真实可以在不同的层次被重新建构。其中两个例子已经进入了科学的工具箱，任何高中学生都可以使用。首先是构成门捷列夫元素周期表的一百多种元素，它们之间的结合产生了所有化学分子。然后是几十个电子或夸克之类的基本粒子，演化出了整个亚原子物理。

数学领域的情况并无不同，整数均可以被拆分为一系列基本数，并可以重新组合成为新的整数。如果重建是通过加法实现的，那么基本数甚至是唯一的，那就是1。每一个整数都可以由0开始，通过该数字数量的1相加得到。虽然看起来是个自循环，但这个过程恰恰是“整数”真正的定义，并于1921年由维特根斯坦在著名的《逻辑哲学论》中首次提出。

若重建的过程是乘法，事情就变得更复杂也更有趣了。首先，我们可以简单地推断出这种情况下也应该存在一些基本数，即无法再被除了1和它本身以外其他数整除的数字。这些数字叫作质数，包括2，3，5，7，11，13……

又一次，我们可以很快地搞明白，每个数字都可以分解为一系列质数。若出现某个数字无法被（除1及它自身以外的）其他数字整除的情况，那么它本身就是质数，拆解就此结束；否则，它就一定能被其他数字整除，因此成为两个因数的产物，这两个因数中的任何一个，要么是质数，要么还可以被其他数整除。

第一种情况下，我们得到了一个构成开端的基本数。如果是第二种情况，只需要重复前面的过程，再获得另外两个因数，以此类推。在除法的力量下，它们不得不保持基本数的形式，因为每做一次除法运算，因数就会变得更小，迟早达到无法再除的程度。

几乎是在无意间，我们展示了一个重要的算术定理：每个整数最终都可被拆分为质数。但实际上，欧几里得在经典作品《几何原本》中，就已天才般地做出了更深入的研究，研究结果更是被称为“算术基本定理”。这一定理说明，这种因数分解是唯一的，无论过程如何，最终得到的质因子均相同，按大小排列后只有一种写法。

所以说，质数确实是算术的砖石，对于一个数字可以提出的最显而易见的问题就是： 它是不是一个质数？ 人们若有足够的耐心，总能得到答案，因为只需要用它一一除以较小数。最后如果能找到至少一个数字可将其整除，那么它就不是质数，反之若找不到这样的数字，那它就是一个质数。

这一切说起来简单，但随着数字不断变大，所需要的验证时间会可怕地增长。只是数百位的数字，所需要的计算时间就已经超过了宇宙的年龄！几百年甚至几千年以来，人们一直在努力缩短进程，减小难度。直到2002年一个快速而准确的判断方法诞生了。三个印度数学家曼英德拉·艾格拉沃（Manindra Agrawal）、尼拉杰·卡亚尔（Neeraj Kayal）和尼汀·萨克塞纳（Nitin Saxena）找到了它。

但很遗憾，他们的研究结果没有提供一个快速和精确的方法分解出合数的因数。相反，却能对所谓P/NP问题给出有效解决方案。 P/NP问题是理论信息学最重要的问题，也是“千禧年七大难题”之一。美国亿万富翁兰顿·克雷，为其中每一个问题的解决方案提供百万美元大奖，基思·德夫林则以这七大难题为主题出了一本同名书（The MillenniumProblems: the Seven Greatest Unsolved Mathematical Puzzles of Our Time）。

信息学之所以对质数感兴趣，是因为最近密码学领域开始使用质数，来创造足够稳定的信息编码方式。这些编码方法的实现前提，即人们认为不可能快速且精确地找到数字的质因子。

在三位印度数学家的研究发布后，全世界的银行、工业、政治家和间谍都开始恐惧了。因为，如果有人再前进一步，就能跳过整个世界的密码系统，那么从银行卡到信用卡，从电话到邮箱，所有的密码都形同虚设。 1994年彼得·秀尔发现了量子计算机关于该问题的演算方法。所以，解决质因数分解问题的另一条途径，便是造出一台量子计算机——这在目前看来还只是纸上谈兵而已。

如果说计算质因子是典型的实用信息学问题，那么分析质数如何分布就是同样典型的理论数学问题。为它们做出了（或者至少是传述了）第一次大跨越的依然是欧几里得的《几何原本》，它解决了“质数的数量是不是有限的”这个问题。

人们也许会这样回答： “质数明显是无限的，因为整数是无限的。” 但是有限字母组成无限单词的例子表明，理由不会这么简单。欧几里得的答案是： “质数是无限的，但并不明显。 ”他的证明过程堪称数学领域之明珠，方法是：假设质数有限，那么总能找到不在它们的集合中的另一个质数。

欧几里得的想法是，把假设有限的那些质数全部相乘，获得的乘积加1，得到的数字显然要么是质数，要么不是。如果它是质数，我们就创造出了一个新的质数。如果不是质数，那它必有一个质因子不属于之前的质数集合，否则它就能同时被该乘积和该乘积加1所得的数字整除，因此也就能被它们的差，即1所整除，但事实是，没有任何一个非平凡数可以被1整除。

尽管数量是无限的，质数的分布却并不平均，而是逐渐减少的。 100之内有25个质数，1000以内168个，10000以内1229个，100000以内9592个……如果要构建一个类似化学中门捷列夫元素周期表的表格来精确表示它们的分布，我们便迎来了千禧年七大难题的另一位成员——所谓的黎曼猜想。