从历史上看，计算一直是数学发展的驱动力。埃及人为了帮助测量田地的大小发明了几何学；希腊人为了确定行星的位置发明了三角学；发明代数学则是为了求解用数学作世界的模型而产生的方程式。 现在计算更加重要了。现代技术很大一部分是以能够迅速计算的算法为基础的，其中包括了从使得CAT（omputed axial tomography，计算机轴向分层造影，也就是常说的CT）扫描成为可能的小波，到为了作天气预报和预测全球变暖而进行的极复杂系统的外推、因特网的搜索引擎后面的组合算法等等。 在纯粹数学中也要进行计算，而许多大定理和猜测，从根本上讲，是由计算经验的启示而得到的。据说高斯，作为一个杰出的计算大师，时常只需要计算一两个例子，就能发现其后面的定理并且给出证明。一方面，纯粹数学有些分支迷失了与其计算根源的联系，另一方面，由于价格低廉的计算能力和方便的数学软件的出现，有助于扭转这样的趋势。 有一个领域，在其中可以清楚地感觉到这种新的对于计算的强调，那就是数论。高斯早在1801年就发出了具有远见的动员令： 把素数从合数中分离开来，并把后者分解为它们的素数因子，我们知道这是算术中最重要又有用的问题之一。它把古代和现代的几何学家们的劳作和智慧吸引到这样的地步，所以再来详细讨论这个问题已经是多余的了。然而，我们必须承认，迄今所提出的一切方法或者仅限于非常特殊的情况，或者过于麻烦和困难，甚至那些大小未曾超出这些可敬的人所编制的表的范围的那些数，对于从事实际计算的人的耐心都是一个考验。而且这些方法完全不能适用于大数……进一步说，科学本身的尊严似乎也要求用一切手段来解决如此漂亮如此著名的问题。 把一个整数分解为素数因子固然是数论中的一个非常基本的问题，但是数论的一切分支也都有计算的成分。而且在有些领域里，有关计算的文献是如此有生命力，所以我们把对于所涉及的算法的讨论当作本身就有数学兴趣的主题。 这个问题的陈述很简单。给定一个整数n>1，要决定它是素数还是合数，而且我们知道一个算法，这就是依次用各个整数去除n，或者会找到一个真因子，这时就知道n是合数，或者找不到，就知道n是素数。例如，取n=269，它是一个奇数，所以没有任何偶数因子；它也不是3的倍数，所以也没有3的任何倍数为它的因子。继续下去，就可以排除5，7，11和13。下一个可能的数是17，但它的平方大于269，这意味着如果269是17的倍数，269必定也是另一个小于17的数的倍数。因为我们已经排除了这一点，所以在试验到13后就可以停止试除，而断定269是素数。 如果真要执行这个算法，可以用17来试除269，然后就会发现，269=15×17+14。这时就会注意到，商15小于17，这就是告诉了我们172大于269。这时就会停下来。 一般说来，因为合数n必有一个真因子d≤√n，在试除过程中，只要排除了√n后，就可以放弃试除，而断定n是素数。 这个直截了当的方法对于用心算来判断一个小的数字是否素数是极好的，而对用机器来计算稍大的数，这个方法也还可以。但是看一下计算时间的尺度变化，就知道这个方法很差，因为如果把n的位数翻倍，则在最坏的情况下所需的时间就要平方，所以这是一个“指数时间”问题。 如果20位的数字的计算时间还可以忍受，请想一想，判断一个40位数需要多长时间，还有成百成千位的数字。一个算法对于更大的输入其运行时间的尺度如何，在把一个算法与另一个算法比较时这是一个最为重要的问题。 与应用试除需要指数时间相对立，考虑一下两个数字的乘法。小学里讲的乘法的算法是取一个数的各位数，用它们依次去乘另一个数，把这样得到的数字按照进位排列成一个平行四边形阵列，然后再作加法，就会得到答案。如果把每一个数的位数都翻倍，这个平行四边形在每个方向上都会大了一倍。所以运行时间就会增加一个因子4。两个数的这种乘法（也就是所谓“长乘法”），是“多项式时间 ”的算法的一个例子；当输入的数的长度翻倍时，其运行时间的尺度变化是增加一个常数因子。 这样就可以把高斯的动员令重新表述如下：是否存在一个多项式时间的算法来把素数和合数区别开来？是否有一个多项式时间的算法能够给出一个合数的非平凡因子？ 现在可能还看不出来它们是两个性质不同的问题，因为都用到了试除法。然而我们会看到，把它们分开来看是方便的，高斯就是这样做的。 现在我们集中于素数的识别。我们想要的是一个计算起来很简单的判据，使得素数满足它，而合数不满足它。有一个老定理，即威尔森定理 可能正合需要。注意到6!=720，而恰好比7的某个倍数小1，而威尔森定理指出，一个整数n>1为素数的充分必要条件是 所以7是一个素数1。当n是合数时这个式子不可能成立。因为如果p是n的一个素因子，而且小于n，则它也是(n-1)!的因子，所以不可能是(n-1)!+1的因子。这样就有了一个关于素性的板上钉钉的判据。然而威尔森的判据并不符合“计算起来很简单”的标准，因为我们不知道有什么计算阶乘 mod 另一个数的特别快速的方法。例如威尔森能预见到268!=-1(mod 269)，因为我们在前面已经知道了269是一个素数。但是如果我们不知道这件事，怎么能够知道268!除以269的余数呢？我们可以逐个因子地乘，这样来算出268!，但是比之试除到17，计算的步数要多多了。 要证明某一件事不可能是很难的 ，事实上，没有一个定理说我们不可能在多项式时间内算出a!(mod b)。我们确实知道一些比完全硬算快得多的方法，但是，迄今为止，所有我们知道的方法都需要指数时间。所以，威尔森定理初看是有希望的，但是除非我们找到了快速计算a!(mod b)的方法，它是没有用处的。费马小定理又如何？费马小定理指出，如果 p 是一个素数，且 a 是任意一个不被 p 整除的整数，那么 a 的 p −1 次方减去 11 能够被 p 整除，即： 注意2^7=128=7×18+2所以比7的倍数多2。或者取3^5=243，经过计算，知道它同余于3(mod 5)。费马小定理告诉我们，如果n是素数，而a是任意整数，则a^n=a(mod n)。如果说计算一个大数的阶乘mod n是很困难的事情，那么计算一个大的幂mod n说不定也很难。 计算一个中等大小的数，看一看是不是有什么思想会跳出来，这并没有坏处。取a=2，n=91，试一试计算2^91(mod 91)。数学中，一个有力的思想是化简 。我们能不能把这个计算问题化为较小的问题呢？注意，如果已经算出了2^45 mod 91而得到同余数例如r_1，则 就是说，只需再做一点小的附加的计算就可以达到目的，而在计算2^45 mod 91时，指数45只是原来的91的一半稍少。怎样做下去就很清楚了，只需把指数再化为比它的一半还少1的22即可。如果 当然，2^22是2^11的平方，如此等等。这个程序不难“自动化”，因为指数序列 可以直接从91的二进位表示1011011读出来，因为这个指数序列的二进位表示恰好是 1，10，101，1011，10110，101101，1011011， 就是1011011从左向右取的各段。很清楚，从其中的一个数到下一个数，或者是翻倍（就是后面添上一个0），或者是翻倍加1（后面添上0以后再用1相加，或者说就是后面添1）。 这个程序的尺度变化也很好。如果n的位数加倍，则它的指数序列也会加倍，而从一个指数转到下一个指数作为一个模乘法，其所需的时间会加上一个因子4。这样，总的运行时间会增加一个因子8=2^3，这就给出了一个多项式时间的算法，称为“幂同余算法 ”(power mod algorithm)。 这样，我们用a=2，n=91来试一试费马小定理。幂的序列现在是 所有这些式子都是mod 91的同余式，而由一项到下一项，或是作一个平方mod 91，或是平方以后再乘上2mod 91。 请稍等一下，费马小定理不是说最后的同余数应该为2吗？是的，但是，是在n为素数时如此。可能你已经注意到91是一个合数，上面的计算结果证实了91确是一个合数。 值得注意的是——这是一个例子——经过计算会证明n是一个合数，但是给不出任何非平凡的因子分解。 请你试一下这个幂同余算法，但是把幂的底数从2变成3。虽然n=91=7×13是合数而非素数，仍然会得到3^91=3(mod 91)，而与费马小定理的结果一致。我敢肯定，你不会跳到91也是素数的错误结论。按照现在的情况，费马小定理有时可以用来识别合数，但是不能用来识别素数。 关于费马小定理还有两件有趣的事要作进一步的说明。第一件是负面的，有一些合数，例如n=561=3×11×17是一个合数，但是对于每一个整数a，费马同余式都成立。这种数n称为Carmichael数 。从素性检验的角度来看，不幸的是这种数为数无穷。但是还有正面的情况，如果从适合以下条件的数对(a，n)中作随机的选择，几乎可以肯定，当x增大时，所选出的数对中，n一定是素数。这个条件就是： 可以把费马小定理和素数的另一个初等的性质结合起来。如果n是一个奇素数（就是n≠2），则同余式x^2=1(mod n)恰好有两个解，就是x=±1。其实，还有一些合数也有这个性质，但是可以被两个不同奇素数整除的合数就没有这个性质。 现在设n是一个奇数，而我们想要决定它是否素数，则可以这样做：设在区间1≤a≤n-1中取某个数a使得 而由上面提到的素数的简单性质知道，若n是素数，必有x=±1。这样，计算 如果发现它并不同余于±1(mod n)，则n必为合数。 现在我们用a=2，n=561来做一个实验。上面已经说过561=3×11×17是一个合数，但是可以换一个角度来看这个数。前面也说过，561是一个Carmichael数，所以容易推出2^560=1(mod 561)，那么 2^280 mod 561又是什么？计算结果又是1，只从这一点，还不能得出561是否合数的结论。不妨再前进一步看2^140 mod 561。因为它的平方2^280同余于1 mod 561，而计算结果则得到2^140=67(mod 561)，这就是说得到了一个其平方不是±1(mod 561)的数。这就说明561不能是素数而只能是合数。 在实际去做的时候也没有必要从大的指数倒退到小的指数。事实上，如果用前面概述的方法来计算2^560 mod 561，则在计算过程中也就顺便算出了2^140和2^280，所以前面的检验方法的这一个推广，更快也更有力。 这里举例说明一个一般原理。设n是一个奇素数，令a为一个不能用n整除的整数。记 称为强费马全同 。这里发生一件奇妙的事情，就是由Monier和Rabin独立证明了的事：这里没有Carmichael数的类似物。他们证明了若在1≤a≤n-1中选择a，则至少有四分之三次选择得到的a会使得强费马全同不成立。 如果只是想在实际上区分素数与合数，而且不坚持想要证明，那么读到这里也就够了。就是说，现在可以操作如下：如果给了一个充分大的奇数n，则可以在区间[1，n-1]中随机地选20个数作为a，然后试着用这些a为底数，看一看会不会发生强费马全同。只要一旦某个a不适合强费马全同，就可以就此止步：数n一定是合数。而若对这20个a都发生了强费马全同，则可以猜测n一定是素数 。 事实上，如果n是合数，Monier-Rabin定理告诉我们，对于20个随机选择的底数a，都有强费马全同成立的概率最多是4^(-20)，这个机会小于万亿分之一。这样就有了一个很了不起的素性的概率检验方法。如果这个检验方法告诉我们n是合数，那么它就一定是合数，而如果告诉我们它是素数，那么，n不是素数的概率小得完全可以忽略不计。 如果区间[1，n-1]中有四分之三的a都能够提供容易的确认奇合数确实为合数的检验方法的关键，那么真正找出一个a来也一定不难。我们能不能从小的a开始，一个一个地试，直到找到a为止？妙极了，但是什么时候停止搜索呢？让我们想一想。我们已经放弃了随机性的力量，而按照顺序从很小的数字开始逐个地寻找作试验的底数a。那么我们能够用似然的论据来论证这些a的性态都是随机的选择吗？它们之间是有联系的。 例如，设若取a=2并没有得出n为合数的证明，则取2的幂为a也不行。理论上说，有可能2和3都不能证明n为合数，但是取a=2×3=6却有可能管用，虽然这并不是很常见的事。所以，让我们把这种似然推理加以修正，并认为各个a取素数值是独立的事件。根据素数定理，到logn log log n为止有大约log n个素数， 所以似然地说，n为合数的概率是 是收敛的，所以选logn log logn为停止点说不定就行了，至少当n很大时是这样。 Miller能够证明稍弱一点的结果，就是取c(logn)^2为停止点就够了，但是他的证明依赖于黎曼假设的一个推广。Bach的进一步工作能够证明，可取c=2。总之，如果这个推广的黎曼假设成立，而且強费马全同对于每一个正整数a≤2(logn)^2都成立，则n为素数 。所以，如果来自另一个数学领域的未曾证明的假设为真，就可以在多项式时间内，用一个决定论的算法来决定n是素数还是合数。 使用这个有条件的检验方法是有诱惑力的，因为如果它说了谎，把一个特定的合数说成了素数，那么，它的失败——如果能够看出来是失败了的话——将使数学中一个最著名的假设得到否证。说不定这样的失败并不是灾难性的。 在1970年代Miller的检验方法以后，不断对我们提出的挑战就是：是否存在一个不需要假设未证明的数学猜想的多项式时间的素性检验方法 ？印度数学家Agrawal等用响亮的“是”回答了这个问题。他们的思想的起点是二项定理与费马小定理的结合。给定一个整数a以后，考虑多项式(x+a)^n，并用通常的二项定理把它展开。在首尾两项x^n和a^n之间的各项，所有的各项的系数都是整数 如果n是素数，它们都可以用n整除。因为n既然是素数，它就没有能被分母的任意因子约去的因子。就是说，这些系数都是0 mod n。例如(x+1)^7等于 而中间的各项系数都是7的倍数。这样，就有(x+1)^7=x^7+1 (mod 7)。 说两个多项式mod n同余，就是说它们的相应系数都mod n同余。 一般地说，如果n是素数，而a是任意整数，则利用二项定理的思想和费马小定理，就可以得到 证明这个同余关系在a=1的简单情况下就等价于n的素性，这只是一个简单的练习。但是和威尔森判据的情况一样，如果事先不知道n是素数，要逐个来验证这些系数都能被n整除，我们还不知道有什么快捷的方法。 然而，对于多项式，我们能够做的事情多于求它们的幂。我们可以求它们的商和余，如同对整数所做的那样。例如， 说g(x)=h(x)(mod f(x))是有意义的，就是指g(x)和h(x)在用f(x)除以后有相同的余式； 说g(x)=h(x)(mod n，f(x))则是指g(x)和h(x)在用f(x)除以后的余式在mod n意义下同余。 和对于整数同余的模算法一样，也可以快速地算出g(x)^n(mod n，f(x))，只要f(x)的次数不太高就行。Agrawal等就提出了这一点。他们有一个次数不太高的辅助的多项式f(x)，使得只要对于每一个整数a=1，2，…，B（这里B不太大）都有 则n一定属于一个集合，其中有素数和一些合数，但是这些合数容易识别出来（并非每一个合数都难以识别，那些具有小素数因子的合数都容易识别）。这些思想合在一起就成了Agrawal等的素性检验方法。要想详细地给出全部论证，就要明确指出所用的辅助函数f(x)和常数B，还要严格地证明正是素数通过了检验。 Agrawal给出了这个辅助函数，它就是简单得非常漂亮的函数 而这里的r有一个很简单的上界大约是(logn)^5。做完这些事情所需的算法的时间界限大约是(logn)^10.5。他们使用了一个数值上不太高效率的工具把时间减少到(logn)^7.5。Lenstra和我提出了一个不那么简单但是效率较高的方法把logn的指数降到了6。我们做到这一点，是由于我们把所使用的多项式的集合扩大到形式为x^r-1的多项式以外，特别是使用了与高斯用直尺和圆规作正n边形的算法有关的多项式。能够用上高斯的著名工具来对他所提出的区别合数与素数这个问题说上什么，这使我们很高兴。 新的素性检验的多项式时间的算法实际用起来很好吗？迄今为止，答案为“否”，竞争太激烈了。例如使用椭圆曲线的算术，使我们想到了一个检验大数的素性的真正好的证明。我们猜想，这个算法的运行时间是多项式时间，但是我们甚至还没有证明到这个算法可以运行到头而停机 。如果到头来、或者在运行可以停机的时候得到了一个合法的证明，那我们就还能忍受在开始的时候不能确定它能行的那种局面。 这个方法是由Atkin和Morain首先提出的，现在已经证明了一个十进制位数超过20000的数的素性，而且此数不是那种具有特殊形式如2^n-1的数，这种特殊形状会使得素性检验变得容易一些。而那个新品种的多项式时间检验方法的纪录只是可怜的300位数。 对于某些特定形式的数，有快得多的素性检验方法。梅森素数就是形如2的某一个幂减去1的素数。人们以为有无穷多个这种形状的素数，但是远未得到证明。目前已知的梅森素数有51个，最大的是
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报 。
