[转帖]搜寻费马数因子

Newton1983 · 发表于 2004-7-2 04:42:03

<

> 搜寻费马数因子
<

>韩雪涛 
<

> 2003年10月10日，一个网络计算小组宣布找到了一个费马数因子：3×22478785+1 ，由此人们得到了截止目前为止最大的费马合数F2478782 。或许有人要问：这个不可思议的大数是通过什么方法证明是合数的？人们又是如何找到它的这个具有746190位数的因子的？或许还有人要问更基本的问题：什么是费马数？什么是费马素因子？

　　为了回答这些疑问，让我们从费马开始。

　　费马：业余数学家之王

　　费马，1601年8月出生在法国一个皮革商人家中，逝世于1665年1月。费马最初的职业是律师，后来以图卢兹议会议员的身份终其一生。他的一生过得极其平凡，没有任何传奇经历。然而这个度过平静一生，性情淡泊的人，却谱写出了数学史上最美妙的故事之一。

　　费马在年近三十开始认真研究数学，并且只是利用业余的时间从事这种研究。然而这并不妨碍他在数学上取得累累硕果。他在几何学、概率论、微积分和数论等众多数学领域都留下了自己的足迹。

　　和R.笛卡儿同时或较早，费马得到了解析几何的要旨，因而与笛卡尔分享着创立解析几何的荣誉；他与帕斯卡在一段有趣的通信中一起奠定了古典概率论的基础，因而与帕斯卡被公认为是概率论的创始人；他提出光学的“费马原理”，给后来变分法的研究以极大的启示；他是创建微积分学的杰出先驱者。

　　任何人，即便只是完成了上述工作中的某一项，就足以使自己在数学史上留下不朽的名声，更不用说能同时拥有这众多的成果了。然而，费马的成就尚不止于此，他将更多的业余时间与精力奉献给了自己最喜爱的消遣：数论。在这方面的研究中，他显示出自己过人的才华，完成了自己最伟大的工作。可以说，近代数论是从费马真正开始的，他是数论发展史上一个承前启后的人物。他提出了为数可观的数论定理，奠定了近代数论的基础，因而他被当之无愧地称之为“近代数论之父”。事实上，在高斯名著《算术研究》出版之前，数论的发展始终是跟费马的推动联系在一起的。如数学史家E.T.贝尔所评价的：费马是一个第一流的数学家，一个无可指摘的诚实的人，一个历史上无与伦比的算术学家。

　　费马数猜想：大师的失误

　　1640年，在数论领域留下不可磨灭足迹的费马思考了一个问题：式子22n+1 的值是否一定为素数。当 n取0、1、2、3、4时，这个式子对应值分别为3、5、17、257、65537，费马发现这五个数都是素数。由此，费马提出一个猜想：形如22n+1的数一定为素数。在给朋友的一封信中，费马写道：“我已经发现形如22n+1的数永远为素数。很久以前我就向分析学家们指出了这个结论是正确的。”费马同时坦白承认，他自己未能找到一个完全的证明。

　　费马所研究的22n+1这种具有美妙形式的数，后人称之为费马数，并用Fn 表示。费马当时的猜想相当于说：所有费马数都一定是素数。费马是正确的吗？

　　进一步验证费马的猜想并不容易。因为随着n的增大， Fn 迅速增大。比如对后人来说第一个需要检验的F5　＝4294967297已经是一个十位数了。非常可能的是，由于这一数太大，所以费马在得出自己的猜想时并没有对它进行验证。那么，它到底是否如同费马所相信的那样是一个素数呢？

　　1729年12月1日，哥德巴赫（哥德巴赫猜想的提出者）在写给欧拉的一封信中问道：“费马认为所有形如22n+1的数都是素数，你知道这个问题吗？他说他没能作出证明。据我所知，也没有其他任何人对这个问题作出过证明。”

　　这个问题吸引了欧拉。1732年，年仅25岁的欧拉在费马死后67年得出F5 ＝641×6700417，其中641=5×27+1这一结果意味着是一个合数，因此费马的猜想是错的。

　　在对费马数的研究上，费马这位伟大的数论天才过分看重自己的直觉，轻率地做出了他一生唯一一次错误猜测。更为不幸的是，研究的进展表明费马不但是错的，而且非常可能是大错特错了。

　　此后人们对更多的费马数进行了研究。随着电子计算机的发展，计算机成为数学家研究费马数的有力工具。但即使如此，在所知的费马数中竟然没有再添加一个费马素数。迄今为止，费马素数除了被费马本人所证实的那五个外竟然没有再发现一个！因此人们开始猜想：在所有的费马数中，除了前五个是素数外，其他的都是合数。如果这一结论被证实，那么对于费马的草率猜想来说，恐怕不会有更为糟糕的结局了。

　　费马数与尺规作图：出人意料的结合

　　二千多年前，古希腊数学家曾深入研究过一类作图问题，即：如何利用尺规作内接正多边形。早在《几何原本》一书中，欧几里德就用尺规完成了圆内接正三边形、正四边形、正五边形，甚至正十五边形的作图问题。然而，似乎更容易完成的正7、9、11……边形却未能做出。让后来数学家尴尬的是，欧几里德之后的2000多年中，有关正多边形作图仍停留在欧几里德的水平上，未能向前迈进一步。因此，我们可以想象得到，当1796年年仅19岁的高斯宣布他发现了正十七边形的作图方法时，会在数学界引起多么巨大的震憾了。

　　不过，高斯的结果多少显得有些奇怪。他没有完成正七边形或正九边形等的作图，却偏偏隔下中间这一些直接完成了正十七边形。为什么第一个新做出的正多边形是正十七边形而不是正七、九边形呢？在高斯的伟大发现之后，问题仍然存在：正七边形或正九边形等是否可尺规完成？或者更清楚地阐述这个问题：正多边形的边数具有什么特征时，它才能用尺规做出？

　　在经过继续研究后，高斯最终在1801年对整个问题给出了一个漂亮的回答。高斯指出，如果仅用圆规和直尺，作圆内接正n边形，当n满足如下特征之一方可做出：

　　1)　n=2m；（为正整数）

　　2)　边数n为素数且形如 n=22t（t+1=0 、1、2……）。简单说，为费马素数。

　　3)　边数 n具有n=2mp1p2p3...pk ，其中p1、p2、p3…pk为互不相同的费马素数。

　　由高斯的结论，具有素数p条边的正多边形可用尺规作图的必要条件是p为费马数。由于我们现在得到的费马素数只有前五个费马数，那么可用尺规作图完成的正素数边形就只有3、5、17、257、65537。进一步，可以做出的有奇数条边的正多边形也就只能通过这五个数组合而得到。这样的组合数只有31种。而边数为偶数的可尺规做出的正多边形，边数或是2的任意次正整数幂或与这31个数相结合而得到。

　　就这样，正多边形作图问题与费马数极其密切地联结在一起了！数学的一大魅力在于：看似全然无关的领域竟能以出人意料的方式彼此联系在一起。透过“数学王子”高斯的杰出发现，人们确实可以从中充分领略到数学的这种魅力。事实上，正是两者这种出乎意料的神秘结合，使人们对费马数有了更为持续不断的兴趣。

　　费马数研究的回顾与现状

　　如上所述，在对费马数的研究中，费马迈出了第一步。他给出正确的结论：前5个费马数都是素数。然后，他做出猜想：所有的费马数都是素数。

　　1732年，欧拉给出F5的素因子分解式：F5＝641×6700417，从而否定了费马的推断。为了得出这一结果，欧拉还研究了费马数的性质，证明了一个重要结论：当n≥2时，费马数F5若有素因子，那么这一因子具有k×2n+1+1 的形式。这样在寻找F5的因子时，就可直接排除掉许多不必进一步检验的无关的数值，从而大大减轻的运算量。正是以此为依据，欧拉只对可能的因子进行试除。最终找到了F5的第一个因子641，最终把F5进行了完全分解。

　　1877年，数学家佩平得出一个重要的判据结果：费马数Fn是素数，当且仅当F5整除3(Fn-1)/2+1 。这个结论对于检验费马数的素性是很有效的。

　　1878年，卢卡斯改进了欧拉的成果，证明费马数Fn若有素因子，那么这一因子具有k×2n+1+1 的形式。通过这一加强后的结论寻找Fn的素因子，从而判断它是否是素数就更为简捷了。实际上，正是这一结论奠定了人们寻找大的费马合数的理论基础。

　　1880年，著名数学家朗道给出F6的素因子分解式：F6＝247177×67280421310721。

　　1905年，莫瑞汉德与韦斯坦证明F7是合数。1908年，这两位数学家利用同样的方法证明F8是合数。证明中使用了上述佩平检验法则。1957年，罗宾逊找到F1945的一个因子：5×21947+1 ，从而证明它是合数。1977年，威廉姆找到F3310 的一个因子：5×3313+1 ，从而证明它是合数。1980年，人们找到F9948的一个因子：19×29450+1 ，从而证明它是合数。1980年，哥廷汀证明 F17是合数。1987年，杨和布尔证明F20是合数。1980年，开勒证明了F9448是个合数，它有因子19×29450+1 。1984年，开勒找到F23471 的一个因子：5×223473+1，从而证明它是一个合数。作为最大的费马合数这一纪录保持了近十年。1992年，里德学院的柯兰克拉里和德尼亚斯用计算机证明了F22 是合数，这个数的十进制形式有100万位以上。这一证明曾被称为有史以来为获得一个“一位”答案（即“是－否”答案）而进行的最长计算，总共用了1016次计算机运算。

　　在对费马数的素因子分解方面，进展要缓慢得多。

　　1971年，布里罕德和莫利逊用连分数法，借助于电子计算机花了一个半小时的机时把F7分解为两个质因子的乘积，这两个质因子一个17位，一个22位。1981年，布瑞特和普拉德利用蒙特卡罗方法花两小时机上时间，对F8进行了分解，求得 F8＝1238926361552897与一个62位素数的积。1990年美国加州伯克莱分校的林斯特拉等人利用数域筛法（nFS）（并借助计算网络）分解了 F9。它是2424833与一个148位数的积。同年，澳大利亚国立大学的布瑞特用ECM算法（椭圆曲线法）分解了F10和F11 。迄今为止，F5 ~F11 ，是人们已经完成标准素因子分解式的费马合数。n＝12、13、15、16、17、18、19、21、23时，对应的费马数已找到部分因子。因此，最小的尚未完全分解的费马数是 F12，它还有一个1187位的因子尚需要分解。 n＝14、20、22、24时已经证明是合数，但还没有找到任何因子。尚未判定是合数还是质数的最小费马数是 F33。

　　费马数因子网络搜寻计划

　　随着计算机的普及，个人电脑开始进入千家万户。与之伴随产生的是电脑的利用问题。越来越多的电脑处于闲置状态，即使在开机状态下CPU的潜力也远远不能被完全利用。而另一方面，需要巨大计算量的各种问题不断涌现出来。鉴于此，随着网络普及，在互联网上开始出现了众多的分布式计算计划。所谓分布式计算是一门计算机学科，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。可以说，这些计划的出现恰好为人们充分发挥个人电脑的利用价值提供了一种有意义的选择。

　　费马数因子网络搜寻计划是这种分布式计算计划之一。在这项计划中，人们打算借助网络加速对费马数的研究。从比较小的费马数 F12~ F23到一般大小的 F24~ F1000再到巨大的费马数F1000 ~F50000 都包含在这一庞大的研究计划之内。正是通过这一网络合作计划，人们得出费马数的许多新发现。仅在2003年，人们就找到了8个费马因数。2003年10月10日，通过这一研究计划人们找到了具有746190位数的费马素因子：3×22478785+1 ，由此人们得到了截止目前为止最大的费马合数 F2478782。2003年11月1日这一研究又宣布了一项最新成果：一个新的费马素因子1054057×28300+1被发现。这同时意味着又一个费马合数F8293的产生。计算机出现之前，在近三百年的时间中，人们仅仅找到了16个费马素因子。而借助于计算机，借助于费马数因子网络搜寻计划，在短短的近半个世纪，人们已经找到了234个费马素因子！

　　加入这项搜索计划，只需要下载有关程序。然后这个程序会以最低的优先度在计算机上运行，这对平时正常使用计算机几乎没有影响。如果你想利用计算机的空余时间做点有益的事情，还犹豫什么？马上行动起来，加入“费马因子搜寻计划”吧。你的微不足道的付出或许就能使你找到一个独一无二的费马素因子，从而使你在数学史上留下小小的一笔呢！

txy · 发表于 2004-9-30 05:35:22

知识无限

txy · 发表于 2004-9-30 05:35:29

知识无限

txy · 发表于 2004-9-30 05:35:29

知识无限

txy · 发表于 2004-9-30 05:35:29

知识无限

txy · 发表于 2004-9-30 05:35:30

知识无限

		自动登录	找回密码
密码			注-册-帐-号