许多大定理和猜测，从根本上讲，是由计算经验的启示而得到的

luyuanhong

许多大定理和猜测，从根本上讲，是由计算经验的启示而得到的

原创 我才是老胡 老胡说科学 2024-03-19 23:01 上海



从历史上看，计算一直是数学发展的驱动力。埃及人为了帮助测量田地的大小发明了几何学；希腊人为了确定行星的位置发明了三角学；发明代数学则是为了求解用数学作世界的模型而产生的方程式。

现在计算更加重要了。现代技术很大一部分是以能够迅速计算的算法为基础的，其中包括了从使得 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 是一个素数。当 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 整除，即：



换句话说，a^(p-1) 除以 p 的余数是 1 。

注意 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 的平方，如此等等。这个程序不难“自动化”，因为指数序列

1，2，5，11，22，45，91

可以直接从 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 被某个大数 x 所限制。

可以把费马小定理和素数的另一个初等的性质结合起来。如果 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 整除的整数。记



t 为奇数，则把



称为强费马全同。这里发生一件奇妙的事情，就是由 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 为合数的概率是



虽然这些素数并不能帮助我们证明 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 个，最大的是





我才是老胡