Science 版 (精华区)

发信人: emacs (In the Name of Love), 信区: Science
标  题: 《阿基米德的报复》第三章  素数的滥用
发信站: 哈工大紫丁香 (2002年07月31日18:05:16 星期三), 站内信件

第三章  素数的滥用




　　


　　原子说——相信事物不可分割——不仅指导着古希腊人研究物质而且指导着
他们对数的研究。欧几里得及其同时代人认识到，某些整数如 2，3，5，7及11
是根本不能被除尽的。这些只能被它们自身和1整除的数被称为素数。那些不是
素数的数——如4，6，8，9，10等等——有另外的除数。这些数被称作合成数
（非素数），因为它们每个数都各自由某些素数“合成”。例如，4＝2×2，6＝
2×3，8＝2×2×2，9＝3×3，及10＝2×5。

　　1985年9月，当休斯敦的谢夫隆地球科学公司对被称为克雷X－MP型的新式巨
型计算机进行使用检验时，它在以每秒做4亿次运算的速度工作了3个多小时后发
现了人（或机器）所知的最大素数。

　　大约在2300年前，欧几里得就证明存在无限多的素数。但迄今还没有人发现
素数的模型或产生素数的有效公式。由于没有模型可参照，发现新的最大已知素
数没有任何窍门，这一发现的新闻不仅迅速地传遍了数学界而且传遍了整个世界。
美国哥伦比亚广播公司《晚间新闻》节目的主持人瓦尔特·克伦凯特专门在电视
上插播了一个素数的轻松故事，而全国公共广播电台仍然有这样一个栏目。

　　谢夫隆计算机求得的创纪录的素数多达65，050位数。这个有65，050位数的
庞大数字是一个梅森数，它等于2的216，091次幂减1，要把这个数全部列出来要
占去本书30页纸。“我们只是偶然地运算了足够的数而得出这一新素数的，”谢
夫隆的一位副总裁告诉新闻界说，“让该机器开动并进行运转，证明它健全无损
是我的职责，其结果是令人感兴趣的……但这些结果肯定无助于发现石油。”

　　寻找更大的素数并探求其性质与寻求奇数完全数一样都是数论的一部分。数
论表面上简单。其主要定理可以表述得人人都可理解，但证明起来——如果是已
知的话——却需要艰深而复杂的数学运算。例如1742年，生于普鲁士的数学家克
里斯琴·哥德巴赫猜想每个比2大的偶数都是两个素数之和。根据这一分析，4＝
2＋2，6＝3＋3，8＝3＋5，10＝5＋5等等。数理论家借助于计算机将1亿以下的
所有偶数都分成为两个素数之和，然而他们却没能证明哥德巴赫的简单猜想是普
遍正确的。而这并不是因为缺乏尝试之故。过去两个半世纪以来，许多最有才能
的数学家都曾思考过这一问题。

　　在数学的所有分支之中，数论传统上一直是最远离物理现实的。数学其他深
奥领域的抽象结果似乎已有效地用于物理、化学和经济之中。而对数论中的多数
结果来说却并非如此。如果哥德巴赫猜想明天得以证明，数学家会欣喜异常，而
物理学家和化学家将不知道如何应用这一成果——如果它确有应用价值的话。因
此，研究素数被认为是最纯的数学，与应用无关的数学。几个世纪前，数论的这
种纯性为它赢得了“数学皇后”的美称。

　　然而在今天，这座宫殿里却出了问题。那最纯的论题——素数正在以国家安
全的名义滥用自己。据报道我们政府所用的某些最好的密码是依靠素数创制的。
在这些密码中，字母被转换成数字，其根据纯然是数学的：某些计算程序较易创
制但极难破译。例如，计算机计算两个100位数的素数的积极其容易。但已知那
个200位数的积去恢复那些素数除数却极其困难（当然，除非有人告诉你）。将
这一点应用于密码使人茫无头绪。将电文译成电码的人必不能破解密码。将电文
译成电码，他只需知道200位数的积。但要破译这段电文他得知道两个素数除数；
而只知道其积是远远不够的。

　　这种密码被称为公钥密码，因为它可以用一种很公开的方式来使用。如果我
想收到秘密信件，我只需公布200位数的数字（并对如何用于编密进行解释）即
可。然后，任何人只要他愿意就可以给我寄编成密码的信。因为只有我一人知道
那两个素数除数，因此也只有我才能轻易地破译那些信件。然而，这种密码系统
起作用的惟一原因是数论学家迄今依然不知如何将巨大的合成数化成构成它们的
素数。

　　佐治亚大学著名的素数学家卡尔·波梅兰斯说：“这种密码系统是对无知的
利用。由于这种密码，更多的人卷入了对数论的研究。而致力于研究分解因子问
题（寻找素数除数）而未获成功的数学家愈多，这种密码就愈可靠。”因此，这
种密码系统的成功又以另一种方式仰赖于数论：要确认那相乘的100位数的素数
必须运用尖端的数学方法。

　　既然素数处于密码学的显要位置，我想考察一下关于素数何为已知的，以及
何为未知的。很久以前，欧几里得就证明素数是无限多的。他2，300年前的证明
依然是数学简明而别致的范例。

　　欧几里得说，我们假设素数是有限的，那么其中之一——我们称之为P——
就会是最大的。现设有一个比P大的数Q，Q等于1加上从1到P所有整数的积。换句
话说，Q＝1＋1×2×3……×P。对于Q来说，很明显，从2到P的所有整数都不能
整除它；每次除都会得出余数1。如果Q不是素数，它就会被某个比P大的素数整
除。相反，如果Q是素数的话，Q本身就是一个比P大的素数。两种可能性都意味
着比最大素数还要大的素数的存在。这当然就意味着，“最大的素数”这概念是
虚设的。但如果没有这样一个怪数，素数就一定是无限的。

　　长期以来，数学家们一直梦想着发现一种公式，运用这个公式代入从0到无
穷大的n的整数值就可以得出所有素数。18世纪的大数学家列奥纳德·欧拉反复
考虑用那个诱人的简单公式n2＋n＋41。如n＝0，该公式则得出素数41；如n＝1，
得素数43；n＝2得素数47。的确，当n为0至39中连续的整数值时，欧拉公式得出
的全是素数。但如n＝40时，这一公式突然不灵了。其得数1，681是41的平方。




欧拉公式

　　1963年，曾在洛斯阿拉莫斯从事早期原子弹研制性工作的卓越数学家斯坦尼
斯劳·乌拉姆在一片纸上随意写出一串数字，它们是连续的整数，从1开始呈方
形螺旋地向外扩展：

乌拉姆的小草笺



　　使他震惊的是，草笺中的素数——我已用线标了出来——都落在了对角纸上。
乌拉姆受到这种偶然发现的鼓舞便与两个助手马克·韦尔斯和迈伦·斯坦一起研
究从除了1之外的整数开始的方形螺线。从41到44的整数也构成了一个螺线。同
样，素数也常常落在对角线上。从421至383这条长对角线与由欧拉的n2＋n＋41
的公式所得出的素数是相对应的。

乌拉姆的大草笺


　　1963年，洛斯阿拉莫斯的马尼艾克二型主机储存了前9，000万个素数。“在
洛斯阿拉莫斯我们也有一台第一流的图解计算设备，”韦尔斯回忆说，“因此我
们对用计算机绘出素数图式感到异常激动。”马尼艾克二型为1，000万以下的所
有素数都绘出方形螺线图。果然，许多数都神奇地出现在对角线上。

　　欧拉公式n2＋n＋41在n为大数值时证明有令人震惊之效。马尼艾克二型计算
出，在1，00O万以下的所有素数中，该公式可得出占总素数的47．5％。而当n值
较低时，该公式工作得更有成效。当n值小于2，398时，得素数的机会一半对一
半。而当n值小于100时，该公式得出86个素数，合成数只有14个。


　　乌拉姆和助手们还发现了其他几乎与欧拉公式同样有效的生成素数的公式。
公式4n2＋170n＋1，847计算1，000万以下素数的成功率为46．6％，并得出760
个欧拉公式所不能推出的素数。公式4n2＋4n＋59的成功率为43．7％，同时得出
大约1，500个不能由其他两个公式推出的素数。

　　最奇怪的是，虽然这些公式都有很高的成功率，虽然在方形螺线中存在明显
的对角线规则，但数理论家已证明与欧拉公式相仿的公式无一能生成全部的素数，
或除素数外别无他物。但这一证明并未阻止浪漫主义者寻找素数的模式。

　　在100以内的数字中有25个素数：2，3，5，7，11，13，17，19，23，29，
31，37，41，43，47，53，59，61，67，71，73，79，83，89和97。这些连续的
素数（以及随后无限多的素数）之间的间隔并无明显的范式可循。由于2是惟一
的偶数素数，2与3也是惟一一对只相差1个的素数。

　　相差2的素数——被称为孪生素数——又如何呢？在前25个素数中有8对孪生
素数：（3，5），（5，7），（11，13），（17，19），（29，31），（41，4
3），（59，61）和（71，73）。大约150年来，数字理论家就推测过，孪生素数
就像素数本身一样是无限多的，但还没有人能证明这一点。在1966年，研究取得
进展，那时，中国数学家陈景润证明：在只相隔两个的无穷对数字中：第一个数
为素数，第二个数也是素数或是两个素数的积。（为两个素数之积的数被称为
“殆素数”，这一叫法既表明了数学家们不可抑制的乐观主义，又证明了真正素
数的发现之难。）

　　乐观主义的另一表现是：陈先生证明了哥德巴赫猜想的较无力那一面的说法：
每个“充分大”的偶数是一个素数和一个殆素数之和。“充分大”是素数文献中
对“我知道我的证明对比某数Q大的所有数都有效，但我不知道Q是多少”的婉语。
虽然短语“充分大”一词模糊不清，数学家们仍然认为陈的证明是过去30年来对
素数理论意义最为重大的发现。

　　人们对素数之间离得多开比素数如何相互靠近知道得更多一些。的确，很容
易证明存在任意长的非素数的连续数列。让n！表示1到n的所有整数的乘积。这
样，n！就可以被从2到n的每个整数整除。试想一下n!＋2，n！＋3，n！＋4……
n！＋n的连续数列。这时，数列中的第一项n！＋2则可被2整除；第二项n！＋3
可被3整除；第三项n！+4可被4整除；等等。在这个数列中有n—1个数，没有一
个是素数。通过任意选择n的大小，你可以得出你想要的无素数的连续整数数列。

　　但也有大量的长串素数数列。事实上，数理论家认为素数可以形成漫长的等
差级数（由同样差分开的素数数列）。较短的等差级数是容易发现的。例如，素
数3，5和7构成3项差额同为2的等差级数。（1944年，有人证明有无限组等差级
数的3个素数。）素数199，409，619，829，1039，1249，1，459，1，669，1，
879和2，089构成一个10项共同差额为210的等差级数。至于更长的级数，由于初
始的素数和共同差额急剧上升，因而难于发现它们。然而，1983年，保罗·普里
查德在康奈尔发现了19个呈等差级数的素数；初始素数为8，297，644，387，共
同差额为4，180，566，390。

　　一些数学家甚至推测存在任意长连续素数的等差级数。例如，连续素数1，
741，1，747，1，753和1，759构成4项差为6的等差级数。然而，现在还没人能
证明这一猜想，更不必说素数不必是连续的等差级数这一根据相对不足的猜想了。

　　对于素数，我们知道什么又不知道什么？对此可写一篇长篇论文。再举一个
简单例子就足已。有人已证明在比1大的任何数和其倍数之间至少有一个素数。
（这个证明的一个令人震惊的后果是：在n位数中至少有3个素数——n可为任何
正整数。）但无人知道在任何比1大的数的平方和其相邻数平方之间是否有一个
素数。

　　既然素数本身没有已知的模式可循，那么数学家在努力证明它们时明显显示
出杂乱无章也许是惟一合适的做法。某些基本定理——如有无限多的素数，它们
之间有任意长的间隔——已简单明了地得以证明。其他定理，如哥德巴赫猜想依
然有待证明。虽然没有一个自重的数学家对其正确性表示怀疑。为取得进展，数
理论家采用了证明关于“殆素数”和“足够大的数”的办法。这一领域需要出现
另一个欧几里得或欧拉。在那之前，我们可能依然处于这种奇妙的状态：依赖于
秘密通讯的政府和工业继续从数学家的无知中获利。

　　对数理论有兴趣的读者不妨对这些未被证明的猜想动动手和计算器。如果猜
想是正确的，证明工作可能会采用技术数学的成果，这是门外汉所做不到的。但
如果与所期望的相反，它们碰巧是错的，全部所需要的则是一个反例。据历史记
载，那些最具数学头脑的人也会出错。欧拉声称，1个5次方的数决不会等于两个
5次方的数、3个5次方的数或4个5次方的数之和。（换句话说，不存在满足等式
x5=y5＋z5条件的整数x、y和z；不存在满足等式a5=b5＋c5+d5条件的整数a，b，
c和d；也没有满足等式m5=n5+o5+p5＋q5条件的整数m，n，o，p和q。）两个世纪
后的1966年，这一断言受到驳斥，因为发现了一个反例：144的5次方正是另外4
个5次方的数——即27，84，110和133——之和。

　　如果推断未获证明的猜想不是你的事，考虑考虑某些数也许是。但不要再犯
哈迪的错误：早早地就把出租车号斥为无趣的。前不久我乘机远行。当我为一本
小说所吸引住时，邻座那位坐卧不安的同伴笨嘴拙舌地试图激起谈兴：“我们乘
坐的是407号飞机。对我来说，这个数似乎很枯燥，我希望它不是个凶兆。”

　　“胡说，”我从书中抬起头来答道，“这个数字一点也不枯燥，相反，它非
常有趣。它是等于其各位数3次方之和的最大的3位数。”那人直盯着我，好像我
是个疯子，但他拿出一张便条开始不停地草算起来。他做了一路的计算，而我却
可以不受打扰地读完我的小说。



--
What a friend we have in EMACS,
  All our text-problems to halt!
What a privilege to keypress
  Control-meta-ESC-shift-alt!

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]