主题：209-陶哲轩：论质数 -- 万年看客

YouTube ... index=7&t=1263s

我今天不想讨论我自己的工作，而是想讨论我正在研究的领域，也就是数论，尤其是对于质数的研究。这是数论的重要组成部分，也是一个很古老的主题，我们已经投入了两千年的时间加以研究。我今天肯定不可能在接下来一个小时之内讲清楚全部研究成果，只能带着大家走马观花地浏览一下，就好像参观巴黎的时候仅仅去看埃菲尔铁塔一样，只能让大家浅尝辄止地领略一点滋味。今天的我们对于质数的了解已经比两千年前多得多了，但是依然有很多需要完成的工作。这依然是一个令人兴奋异常的领域，每年我们依然还在取得很多研究成果。

我们先来看看定义，所谓质数就是大于1且不能被表达为另外两个较小自然数乘积的自然数。换句话说，2、3、5都是质数，4则不是。画面上列举了前二十个质数。我们为什么关心质数？打个比方，质数就好比化学当中的元素原子，是自然数乘法运算的基本构件。这一点源自公元前300年左右欧几里德最早提出的质数定理，这也是算术的根本理论：任何一个大于1的自然数都可以表达为不少于一个质数的乘积。就好像每一个分子都可以被分裂成原子一样，每一个自然数也都可以被分解成一系列质数。此外每一个自然数都只有一种全质数乘积表达方式——在这里乘数顺序无关紧要——比方说50就只有2×5×5这么一种可能，5×5×2也是一回事。因此我们不认为1是质数，因为1不能被分解成更小的自然数.此外如果将1规定为质数，那么基本定理就不能为真。因此我们不能向1授予质数的会员身份

这是质数之所以重要的第一个原因。关于质数的另一项有趣定理在于质数的数量很多。根据欧几里得定理，质数的数量是无限的，相比之下化学元素的数量总共也就126种左右。乘法与加法在这方面截然不同。如果我们倚靠加法而非乘法来定义质数，那么唯一的质数就是1，因为所有的自然数都可以被分解为若干个1相加。其实我还挺想向大家证明一下这条定理，不过我知道台下坐着的都不是专业数学从业人员，所以我也不会涉及真正的数学细节。下面这条证明非常简洁且美丽，所以一定要给大家看一看。这条证明利用了数学证明当中的一项有力工具，也就是归谬法。你想证明某条定理就先假设这条定理为假，然后再证明这条定理不可能为假，因而间接地证明定理为真。英国数学家G.H.哈代曾经说过：“归谬法是远比任何象棋开局更加高明的开局。在象棋开局当中，棋手往往会让给对方一个车甚至一个后从而赢得比赛，数学家却会将整个棋局都让给对手但是依然获得胜利。”首先我们假设质数的数量是有限的。然后我们给每一个质数编号，从P1到P2直到Pn。再假设2、3、5是唯一存在的质数。然后你将所有这些质数相乘并且将乘积加1或者减1，比方说2×3×5，结果是30。加1或减1，结果要么是29要么是31。这一下子我们就又有了相差2的两个质数。这两个数字都大于一，而且也都不能被之前的任何一个质数整除，这样一来我们就构建了两个不能被任何质数整除的新数字，于是就与原本的定理相悖了。因此质数不可能是有限的，必须是无限的。

这是一条很简洁的证明，也是一条间接证明。它只能告诉你存在无限多的质数，却不能告诉你这些质数都在哪里。还有很多直接证明质数无限的证明方式，但是都不如这项证明简短或者优美。因此我们从理性上知道存在着无限多个质数，但是我不能向大家展示这么多质数。实际上我们现在已知的质数数量的确是有限的。根据世界纪录，已知的最大质数是2的32582657次方减1。这个质数的数位几乎有1000万位这么长，依靠分布式互联网的计算才得以确证这个数确实是质数。

根据欧几里得的证明，我将许多质数相乘然后加1或者减1，于是就得到了一对孪生质数，也就是相差2的质数。P是质数，且P+2也是质数。比方说3与5是一对孪生质数，5与7，11与13，17与19，29与31，41与43，等等。尽管欧几里德在自己的着作当中从未指明这一点，但是我们难免想当然地推测，既然存在无限多的质数，那也肯定存在无限多的孪生质数。既然欧几里得定理的证明很简单，那么孪生质数定理的证明应该也不难。但是即便在两千年的研究之后，我们依然不能确定这个猜想是真是假。你或许觉得我们只要将若干质数相乘然后加1或减1就肯定能得到新质数，但是并非如此。比方说将前四个质数2、3、5、7相乘之后减1得到209，不过这个数字并不是质数。209确实不能被2、3、5、7整除，但是可以被11和19整除。已知的最大孪生质数是2003663613乘以2的195000次方加减1.这对孪生质数各有五万八千多位，而且就是在本周周一被人发现的。我昨天才刚刚读到这项研究成果，不得不临时修改幻灯内容。之前的记录是五万一千多位，这次他们一下子就超出了七千位数。

为什么质数问题如此难以理解？因为我们并不特别理解质数的序列。比方说以下这个序列，2，3，5，7，11。这个序列看上去任意无章，至少远比其他数列更加随机，比方说平方数数列1，4，9，16，25，这个数列要有序的多，因为只要看一眼这个数列的前几项我就能告诉你这个数列的第1000项是什么——是100万。但是我无法张口就来地告诉你第1000个质数是什么，首先必须要做很多工作。因此第n个质数常被称作Pn，我们还没有计算Pn的好方法，至少没有很好用的公式。只有一个质数数列，这个数列的每一项都早已注定，只是看上去很随机而已。二十世纪着名数学家保罗.埃尔德什引用过爱因斯坦早期的一句话。爱因斯坦不相信他的同事们给出的量子物理的哥本哈根诠释，因为这似乎意味着宇宙具有根本上任意性。爱因斯坦宣称：“上帝不会与宇宙掷骰子。”埃尔德什则表示：“上帝或许不会与宇宙掷骰子，但是祂肯定拿着质数玩得挺开心。”

目前我们并不能准确地计算出第n个质数，但是我们有一个不很确切的公式。如果你满足于Pn的近似值，那么我确实可以给你提供一个准确度当高的近似值。这条定理名叫质数定理，于一百多年前得到证明。这条定理指出，Pn约等于n乘以n的对数。这里的对数不以10为底数，要不然就太奇怪了。因为质数不会关心我们还长着十个手指头。这里的对数是自然对数，底数是e，也就是2.71828……。这是一条非常奇怪的定理，一般被公认为数论领域的最伟大成就，甚至是唯一的成就。他的证明要采用远远更加先进的数学，而且这个结果也远比看上去更深刻。我这里给大家一个类似作弊的简化证明版本。让大家理解一下这条定理多么犀利。

我要用很多不准确的术语。首先我们按照下列方式分析质数，首先创造一道所谓的音波——准确的称呼是曼戈尔特函数——这道音波在时间为质数时发声，在其他时间保持安静。换句话说，在1的时候保持安静，在2的时候出声，在3的时候出声，在4的时候安静，等等。这则公式表达的就是每一声音量。这是一道非常有趣的声波。因为你可以将其当做一个函数。然后我们倾听这个函数——或者说对其进行傅里叶变换——当然这话说得依然不太准确，实际进行的是梅林变换，与傅里叶变换差不多——你会注意到音波当中的特定音符。这些音符是黎曼Zeta函数当中的0值——这个函数我就不讲了——被称作“质数的音乐”。每一个音符都会揭示某种隐藏的质数分布模式，因为声波按照某一特定频率震荡就会体现为一个音符。从原则上来说，只要知道这些音符是什么，就可以复原整个质数序列。仔细看看全部有可能出现在这场所谓质数音乐剧当中的音符，就会发现其中有很多音符并不会出现。这一点不仅展现出来很费事，想要证明更费事。但是一旦你能够从乐曲当中排除某些音符，就能更好地理解乐曲的意义。要么利用傅立叶分析或者与其关系密切的复分析都可以证明这条定理。

还有其他更初等的方法可以证明质数定理，但是这些证明方法都更长，也并不特别符合直觉。初等证明远远不如上述的现代证明那样优美，而且也揭示不了多少信息。这里我举几个例子：第1000个质数是7919，而n取1000时n乘以对数n得到6907，与正确答案差了13%。如果我们再看看第100万个质数，第10亿个质数，甚至于第1万亿个质数，就会看到这个误差就会越变越小，但是始终不如人意。这条定理主张随着你在质数序列上越走越远，误差将最终趋近于零。

在数学当中能够证明初始结果固然很好。但是用来证明结果的技巧要比结果更加重要，因为同样的技巧还可以用来证明其他结果。比方说质数定理也可以用来证明其他结论，我这里举两个例子。比方说我们来看一个大质数，也就是任何大于5的质数，以十进制表示这个质数的最后一位，那么这个尾数必然只能是1、3、7或者9，不可能是4、6、8或者0。尾数为2或者5的例子各自只有一个。这一点看上去显而易见，不这么显而易见的是另外一项主张：各个尾数结尾的质数数量相等，以1结尾的大质数的数量相当于以3、5或者9结尾的大质数数量，这4个尾数各占全部质数的25%。这项事实并没有这么显而易见，证明起来也费了不少力气。用十进制以外的其他进制同样可以表述这一主张。

另一项关于质数的着名定理于1937年被提出：任何足够大的奇数都可以写成三个质数之和。这个猜想最早由十八世纪的业余数学家哥德巴赫提出，哥德巴赫当年主张任何大于五的奇数都可以表达为三个质数加和，例如7等于3+2+2。他猜想一切奇数都可以这样表示，然后1937年维诺格拉多夫证明了任何足够大的奇数都可以写成三个质数之和。那么到底多大的奇数才算足够大？多年来这项标准的门槛再一次降低，2002年我们证明了任何大于10的1346次方的奇数都是三个质数的加和。通过另一种截然不同的方法，我们还证明了任何小于10的20次方的大奇数也都是三个质数的加和。我希望有朝一日这两者之间的鸿沟能够得到弥合，但是目前最优秀的计算机也无法证明10的1000次方以下的奇数同样符合这一定律，而这个数字已经超过了宇宙当中所有的原子数量。所以依靠暴力穷举（brutal search？）无法证明这一点。还有一条关于偶数的哥德巴赫猜想，比奇数猜想更加难以证实：一切大于2的偶数都是两个质数之和。这项猜想至今尚未被证实，实际上它的难度堪比孪生质数猜想。

所以质数定理告诉了我们第n个质数的值大约是Nlgn，但是实际上还有一个在我们看来更加精确的公式可以计算这个数值。臭名昭着的黎曼假设预言了一套更精确但也更复杂的公式来计算第N个质数。这一假设问世已有150年，是数论领域最重要的未解之谜。波士顿大学的克雷数学研究所将这套公式的证明列为了新千年七大悬赏数学难题之一，能够证明这个问题的人可以得到100万美元奖金。黎曼主张质数的音乐按照和弦的方式排列，但是这句话本身就非常难懂。为了体现这套算法的结果多么准确，我们来看看这套公式计算第1000个、第100万个，第10亿个以及第1万亿个质数的结果。表格右边是黎曼假设给出的数值，可以看出这套算法的误差非常小。这套算法无法预测第n个质数究竟是什么，但是可以给出相当精确的估计值。第一千个质数的估算结果还有接近2%的误差，但是到了第1万亿个质数时误差就降到了0.0002%。

黎曼假设并不是准确的计算公式，可以看到公式中有一个大写的O，代表我们目前还不理解的误差项。假设质数的排列当真完全随机，假设上帝将所有的数字洗牌，任意抛出质数，那么产生的误差项就应该相当于这个误差项。某种意义上你会期望黎曼假设的预测基于大数定律也体现这样的误差。黎曼假设主张质数的分布看上去的确随机。我们将这种现象称作伪随机，实际上并不随机，只是看上去很随机。就好比计算机里的随机数生成器，其结果也并非随机，而是基于一套非常复杂的算法使其看上去好像随机。但是我们并不擅长证明事物的随机性。或许1万亿之前的质数都是随机分布的，但是到了1万亿之后就会突然凑在一起，留下很大的空白。我们不能确定质数会不会在大到一定程度之后就背着我们搞阴谋，我们现在还看不透这一点。我们怎样才能知道质数不会搞阴谋可能是个哲学问题，但是目前我们还没有很好用的工具来预防这一点。

以上都是纯数学的内容，但是证明质数的分布是伪随机并不是单纯的学术问题，这一点关系到互联网安全以及银行安全。这些安全体系基于以下理念：质数的分布的确就像数学家预测的那样随机。几十万亿美元的安危完全依靠我们对于质数的信念来维系。这方面的实际应用例证是发明于1976年的Diffie-Hellman密钥交换协议。假设有两个相互陌生的人爱丽丝与鲍勃，爱丽丝想要向鲍勃传递一条秘密信息，但是只能通过非秘密的渠道——例如互联网——来发送。互联网上的每一个人都可以浏览任何其他人的通讯内容，这种情况下你要怎么传送秘密数字？姑且假设这个秘密数字是你的银行账户密码，怎样才能够将这个数字从A传到B，而不必担心途中有任何窃听者破解秘密，尽管互联网完全开放？如果两个人并不是陌生人，而是事先见过，那么他们可以约定一套密码，但是他们不能这么做。现在他们只能在公开网络上约定密码，所有人都会听见他们说什么。这是个数字化的问题，但是我们可以进行物理比喻。比方说爱丽丝想给鲍勃寄一封实体信件，用信封装的那种，但是他知道他的全部信件都会在邮递途中被人拆开看。那样的话要怎样传递秘密信息？你必须要玩一点把戏。爱丽丝可以将自己的信息锁在盒子里，在盒子上加一把锁。爱丽丝自己拿着钥匙，然后将挂了锁的盒子寄送给鲍勃。打开邮包的人们只能看见一个上锁的盒子，他们打不开。当然鲍勃也没有钥匙，所以打不开。但是鲍勃可以在这个盒子上再加挂一把锁，然后把盒子再寄回给爱丽丝。爱丽丝打不开鲍勃的锁，但是她可以打开自己的锁，然后把这个盒子再寄回去。鲍勃打开盒子就可以阅读信息了。这样一来爱丽丝与鲍勃没有必要事先通气就可以传递秘密。

以上是实体问题的解法，在数字领域这个问题依靠类似的方法来解决。假如爱丽丝想要将一个秘密数字g发送给鲍勃，首先两人随意约定一个足够大的质数p，然后爱丽丝挑选一个数字秘钥a来为原始数字加密，在数学上这样加密的方法就是计算g的a次方，将它对p取模。然后你将这个上了锁的数字发送给鲍勃。鲍勃无法将这个数字解密，但是他可以用自己挑选的数字秘钥b对已经加密的数字再次进行加密，即计算“g的a次方”的b次方（模p），也就是g的“a乘b”次方（模p）——现在这个数字被双重加密了——然后将新数字发还给爱丽丝。爱丽丝对双重加密后的数字在模p意义下开a次方，就得到了g的b次方（模p），然后将这个解密后的数字发送给鲍勃。鲍勃以数字b对一次解密的数字进行二次解密，（在模p意义下）开b次方，最终就得到了原本的秘密数字g。

我们其实并不能证明这种做法当真安全，窃听者完全有可能在合理时间内破解密码。我们不知道这一主张是否正确，我们相信这套体系是安全的，但是没有证据。这就又涉及到了另外一个新千年七大数学难题，也就是P=NP。假如P确实等于NP，那么我们就能做很多事情，包括破解这个密码。实际上到那时我们可以破解任何密码，但尤其容易破解这一个。如果P不等于NP，那么这个密码就破解不了。我们并不知道这一点是否正确，但是我们掌握了些许数据。我的朋友让.布尔甘最近有一项研究我特别喜欢，研究表明窃听者借助这一协议拦截的数据——包括g的a次方，g的b次方，g的ab次方以p取模——其中的有效数字“均匀分布”。具体来说，你无法将这些数字的分布与随机噪音区分开来，而解码随机噪音只能得到更多的随机噪音。但是这里审视的仅仅是有效数字。如果窃听者得到了全部数字，说不定他依然能够破解密码。我之所以特别喜欢这份研究是因为它采用了我几年之前的另一项研究成果

下面是几项免责声明，首先我之前的描述并不是协议的运作方式，而是过度简化的比喻。其次，我提到了两种伪随机，黎曼假设是一种，人们相信使得Diffie-Hellman协议足够可靠伪的随机是略微不同的另一种，这两者的精神很相似，但并不是一回事。有些不够准确的新闻报道声称只要解决了黎曼假设就可以开始破解密码，这种说法并不完全正确。这两者并没有直接联系，只是在精神上有瓜葛而已

我接下来的话题是质数数论的另一个重要组成部分，也就是筛选理论。我谈到质数的分布看似随机，但其实并不真正随机。质数还是呈现出了某些非常明显的模式。例如几乎所有质数都是奇数，只有一个例外。几乎所有的质数都与6的倍数相邻——这次有两个例外。质数不能被2或者3整除，除非他们自己就是2或者3。筛选理论是我们用来理解质数的重要工具。根据筛选理论，我们不能单独审视每一个质数——这样做很困难——而是要整体性地审视一组质数。假设你想搞清楚一盒沙子有多少粒，一粒一粒的数非常费事也非常无聊。你可以将整盒沙子称重，然后除以一粒沙的平均重量，就可以让你得到相当可靠的近似值。采取整体而非个体视角，就能更加有效地解决问题。筛选理论试图将质数作为一个集合来加以发现。不妨将质数理解为隐藏在石头当中的雕像，全体自然数就是那块花岗岩，我们想要将藏在里边的质数凿出来。一开始我们先用大锤敲掉大块石头，然后改用较为精细的凿子去掉小块石头，再然后改用镊子进行精细加工，这就是筛选理论的工作原理。

最着名的质数筛我们在中学就学到过，也就是可以追溯到公元前二百年的爱拉托逊斯筛法。假设取一个数字N，例如N是100万，那么我们就可以利用这个筛法求得N的平方根与N之间的全部质数，也就是从一千到100万之间的全部质数。这就好比一大块花岗岩，首先我们抛弃掉所有的偶数，然后抛弃掉所有3的倍数，然后是5的倍数，7的倍数，11的倍数……就这样筛选掉1000以内所有质数的倍数——其中最大的是997——完成这项操作之后剩下的所有数字都是质数。出于种种原因，这并不是一个特别高效的质数筛。我们如今还有更加先进的筛选法可用，当然也更加复杂，更像是学生入学申请表。我们向每一个数字赋予不同的分值或者权重，如果你是2的倍数，权重就降低，不是2的倍数，权重就升高，等等。权重的升降取决于统计数据，到最后如果最终权重值高于某个阈值，你就可以成功入学。从一批数字当中去除掉所有偶数很好理解，抛弃掉3的倍数也很好理解，最后剩下的就是与6的倍数相邻的数。但是数字一大算起来就麻烦了，我们还没能完全依靠质数筛来找到全部质数，但是我们可以将筛选过程中途叫停，这时你还没有抛弃足够多的数字。除了真正的质数之外，剩下的数字里还有一些贴近质数的近似质数。这些近似质数本身不是质数，但是质因子数量非常少，或许只有两三个。尽管我们不很理解质数，但是对于近似质数却非常了解。有一条非常经典的结论名叫陈氏定理。你们还记得孪生质数假设，即存在无限多的质数P，且P加2同样也是质数，我们还没能证明这一点，我个人很想看到它得到证明。目前陈氏定理已经证明了存在无穷多的质数P，且P加2要么是质数，要么是两个质数的乘积。这几乎已经等效于孪生质数猜想了。就很多方面来说这正是筛选理论的极限。我们知道筛选理论的表现不可能比这更好。

最后我来谈一下我本人的工作，正如我刚才所说，即便过去了两千多年，我们依然没有发现质数的分布有什么模式，依然不知道要如何寻找孪生质数，还有很多事情谁也不知道应该怎么做——比方说我们不知道应当如何寻找由两个质数加和而成的大偶数——但是有一套模式我们确实可以有所作为，因为我们发现了作弊手段。这里指的是等差数列。所谓等差数列就是间隔均等的一系列数字。几年前我与本.格林共同证明在质数当中包含着任意长度的等差数列。我不能告诉你这些数列位于哪里，但是我可以告诉你数列的长度想要多长就有多长。对于任何给定值K来说，质数当中都包含着无限多长度为K的等差数列。之前我们证明了长度为3的质数等差数列有无穷多个，现在我们证明了任何长度的质数等差数列都有无穷多个。这里举几个例子：长度为1的数列是2；长度为2的数列是2、3；长度为3的数列是3、5、7，依次类推。

以上几组数列看上去还很小，似乎也很容易寻找，但是当长度为7的时候，找起来就已经不容易了——7,157,307,457,607,757。我们目前确切知道的最长长度是23，但是其中最大的质数已经达到了56万亿，质数之间的间隔已经达到了44万亿，必须动用计算机才能找出这样的数字。我们还不知道24级质数等差数列包含哪些数字，我们只能证明24、25乃至26项的数列都肯定存在。我肯定不可能跟大家说清楚这一点究竟是怎么证明的，不过我可以简短说两句。筛选理论不能告诉我们质数包含长等差数列，但是可以告诉我们近似质数包含长等差数列。我们能找到很多很多由近似质数组成的长等差数列。质数是近似质数的子集，但是我们不知道质数在近似质数当中的分布，可能分布的比较平均，也可能分布得非常有结构。我与本提出了两项论证，表明无论质数在近似质数的子集当中如何分布，是随机还是有结构，都必须包含它所在的近似质数母集当中的等差数列的一部分。就好像近似质数集合包含某种遗传特性，如果母集包含大量的等差数列，那么子集也会包含大量的等差数列。这一点只对等差数列成立，对于孪生质数并不成立。这项猜想不能用来证明孪生质数，但是等差数列的性质似乎有所不同。

我们还有很多工作要做，我们的定理并不能告诉你去哪里寻找长度100万的数列，但是我们也能帮上一点忙。你要想找到长度为k的质数等差数列，那么我们可以肯定这个数列里的所有数字都会小于2的2次方的2次方的2次方的2次方的2次方的2次方的100K次方。我们的猜想提出的上限是K的K次方，仅仅乘方一次。但是这里则乘方了整整7次。我们的证明还有很多不足之处需要加以改进。比方说假如黎曼假设为真，那么我们可以少乘方一次，将上限压低到2的2次方的2次方的2次方的2次方的2次方的100K次方，剩下的还是少不了。就说这么多吧，谢谢大家。