十萬(wàn)美元的懸賞——互聯(lián)網(wǎng)梅森素數大搜索

　　一、價(jià)值五萬(wàn)美元的素數

　　2000年4月6日，住在美國密歇根州普利茅茨的那揚·哈吉拉特瓦拉(Nayan Hajratwala)先生得到了一筆五萬(wàn)美元的數學(xué)獎金，因為他找到了迄今為止已知的最大素數，這是一個(gè)梅森素數：

　　26972593-1。

　　這也是我們知道的第一個(gè)位數超過(guò)一百萬(wàn)位的素數。精確地講，如果把這個(gè)素數寫(xiě)成我們熟悉的十進(jìn)制形式的話(huà)，它共有兩百零九萬(wàn)八千九百六十位數字，如果把它以這個(gè)形式寫(xiě)下來(lái)，大約需要150到200篇本文的篇幅。

　　可是哈吉拉特瓦拉先生并不是一個(gè)數學(xué)家，他甚至很可能對尋找素數的數學(xué)理論一無(wú)所知--雖然這使他贏(yíng)得了這筆獎金。他所做的一切，就是從互聯(lián)網(wǎng)上下載了一個(gè)程序。這個(gè)程序在他不使用他的奔騰II350型計算機時(shí)悄悄地運行。在經(jīng)過(guò)111天的計算后，上面所說(shuō)的這個(gè)素數被發(fā)現了。

　　二、梅森素數

　　我們把一個(gè)大于1的自然數叫作素數，如果只有1和它本身可以整除它。如果一個(gè)比1大的自然數不是素數，我們就叫它合數。1既不是素數，也不是合數。

　　比如說(shuō)，你很容易就可以驗證7是一個(gè)素數；而15是一個(gè)合數，因為除了1和15外，3和5都可以整除15。根據定義，2是一個(gè)素數，它是唯一的偶素數。早在公元前三百年的古希臘時(shí)代，偉大的數學(xué)家歐幾里德就證明了存在著(zhù)無(wú)窮多個(gè)素數。

　　關(guān)于素數，有許多既簡(jiǎn)單又美麗，但是極為困難的，到現在還沒(méi)有答案的問(wèn)題。其中有著(zhù)名的哥德巴赫猜想，它是說(shuō)任何一個(gè)大于6的偶數，都能表示為兩個(gè)奇素數之和。還有孿生素數問(wèn)題。象5和7，41和43這樣相差2的素數對，被稱(chēng)為孿生素數。孿生素數問(wèn)題是說(shuō)：是不是有無(wú)窮多對孿生素數？這里要順便提一下的是，這些看起來(lái)很簡(jiǎn)單的數學(xué)問(wèn)題，它們的解決方法將一定是極其復雜的，需要最先進(jìn)的數學(xué)工具。如果你不是狂妄到認為幾百甚至幾千年來(lái)所有在這些問(wèn)題上耗費了無(wú)數聰明才智的數學(xué)家（有許多是非常偉大的）和數學(xué)愛(ài)好者加起來(lái)都不如你聰明，就不要試圖用初等方法去解決這些問(wèn)題，徒費時(shí)間和精力。

　　古希臘人還對另一種數感興趣。他們將它稱(chēng)為完美數。一個(gè)大于1的自然數叫完美數，如果它的所有因子（包括1，但不包括本身）之和等于它本身。比如說(shuō)6=1+2+3就是最小的完美數，古希臘人把它看作維納斯也就是愛(ài)情的象征。28=1+2+4+7+14是另一個(gè)完美數。歐幾里德證明了：一個(gè)偶數是完美數，當且僅當它具有如下形式：

　　2p-1（2p-1）

　　其中2p-1是素數。上面的6和28對應著(zhù)p=2和3的情況。我們只要找到了一個(gè)形如2p-1的素數，也就知道了一個(gè)偶完美數；我們只要找到所有形如2p-1的素數，也就找到了所有偶完美數。所以哈吉拉特瓦拉先生不但找到了世界上已知的最大的素數，還找到了世界上已知的最大的偶完美數。嗯，你要問(wèn)，關(guān)于奇完美數又是怎么樣的情況？回答是：我們現在連一個(gè)奇完美數也沒(méi)有找到過(guò)，我們甚至根本不知道是不是有奇完美數存在。我們只知道，要是有奇完美數存在的話(huà)，它一定是非常非常大的！奇完美數是否存在這個(gè)問(wèn)題，也是一個(gè)上面所說(shuō)的既簡(jiǎn)單又美麗，但是極為困難的著(zhù)名數學(xué)問(wèn)題。

　　有很長(cháng)一段時(shí)間人們以為對于所有素數p，

　　M_p=2p-1

　　都是素數（注意到要使2p-1是一個(gè)素數，p本身必須是一個(gè)素數，想一想為什么？）但是在1536年雷吉烏斯(Hudalricus Regius)指出，M_11=211-1=2047=23*89不是素數。

　　皮特羅·卡塔爾迪(Pietro Cataldi)首先對這類(lèi)數進(jìn)行了系統的研究。他在1603年宣布的結果中說(shuō)，對于p=17，19，23，29，31和37，2p-1是素數。但是1640年費爾馬使用著(zhù)名的費爾馬小定理（不要和那個(gè)費爾馬大定理混淆起來(lái)）證明了卡塔爾迪關(guān)于p=23和37的結果是錯誤的，歐拉在1738年證明了p=29的結果也是錯的，過(guò)后他又證明了關(guān)于p=31的結論是正確的。值得指出的是，卡塔爾迪是用手工一個(gè)一個(gè)驗算取得他的結論的；而費爾馬和歐拉則是使用了在他們那時(shí)最先進(jìn)的數學(xué)知識，避免了許多復雜的計算和因此可能造成的錯誤。

　　法國神父梅森(Marin Mersenne)在1644年他發(fā)表了他的成果。他宣稱(chēng)對于p=2，3，5，7，13，17，19，31，67，127和257，2p-1都是素數，而對于其它小于257的素數p，2p-1都是合數。今天我們把形如M_p=2p-1的素數叫做梅森素數，M_p中的M就是梅森姓氏的第一個(gè)字母。

　　用手工來(lái)判斷一個(gè)很大的數是否素數是相當困難的，梅森神父自己也承認他的計算并不一定準確。一直要等到一個(gè)世紀以后，在1750年，歐拉宣布說(shuō)找到了梅森神父的錯誤：M_41和M_47也是素數�？墒莻ゴ笕鐨W拉也會(huì )犯計算錯誤--事實(shí)上M_41和M_47都不是素數。不過(guò)這可不是說(shuō)梅森神父的結果就是對的。要等到1883年，也就是梅森神父的結果宣布了兩百多年后，第一個(gè)錯誤才被發(fā)現：M_61是一個(gè)素數。然后其它四個(gè)錯誤也被找了出來(lái)：M_67和M_257不是素數，而M_89和M_107是素數。直到1947年，對于p<=257的梅森素數M_p的正確結果才被確定，也就是當p=2，3，5，7，13，17，19，31，61，89，107和127時(shí)，M_p是素數�，F在這個(gè)表已經(jīng)被反復驗證，一定不會(huì )有錯誤了。

　　下面是我們現在知道的所有梅森素數的列表：（我們注意到梅森神父的名字不在上面--這種素數已經(jīng)由他的名字命名了，就把榮譽(yù)分給最后確認者吧。）

　　序號 p M_p的位數 相對應的 確認 確認人

　　完美數的 年代

　　位數

　　1 2 1 1 ---- ----

　　2 3 1 2 ---- ----

　　3 5 2 3 ---- ----

　　4 7 3 4 ---- ----

　　5 13 4 8 1456 佚名

　　6 17 6 10 1588 Cataldi

　　7 19 6 12 1588 Cataldi

　　8 31 10 19 1772 Euler

　　9 61 19 37 1883 Pervushin

　　10 89 27 54 1911 Powers

　　11 107 33 65 1914 Powers

　　12 127 39 77 1876 Lucas

　　13 521 157 314 1952 Robinson

　　14 607 183 366 1952 Robinson

　　15 1279 386 770 1952 Robinson

　　16 2203 664 1327 1952 Robinson

　　17 2281 687 1373 1952 Robinson

　　18 3217 969 1937 1957 Riesel

　　19 4253 1281 2561 1961 Hurwitz

　　20 4423 1332 2663 1961 Hurwitz

　　21 9689 2917 5834 1963 Gillies

　　22 9941 2993 5985 1963 Gillies

　　23 11213 3376 6751 1963 Gillies

　　24 19937 6002 12003 1971 Tuckerman

　　25 21701 6533 13066 1978 Noll & Nickel

　　26 23209 6987 13973 1979 Noll

　　27 44497 13395 26790 1979 Nelson & Slowinski

　　28 86243 25962 51924 1982 Slowinski

　　29 110503 33265 66530 1988 Colquitt & Welsh

　　30 132049 39751 79502 1983 Slowinski

　　31 216091 65050 130100 1985 Slowinski

　　32 756839 227832 455663 1992 Slowinski & Gage

　　33 859433 258716 517430 1994 Slowinski & Gage

　　34 1257787 378632 757263 1996 Slowinski & Gage

　　35 1398269 420921 841842 1996 GIMPS

　　36 2976221 895932 1791864 1997 GIMPS

　　37 3021377 909526 1819050 1998 GIMPS

　　?? 6972593 2098960 4197919 1999 GIMPS

　　是不是有無(wú)窮多個(gè)梅森素數呢？數學(xué)家們目前還無(wú)法回答這個(gè)問(wèn)題。

　　三、尋找更大的素數

　　為什么要尋找梅森素數？為什么要打破已知最大素數的紀錄？這有什么用處呢？

　　如果你所說(shuō)的用處是指能夠直接創(chuàng )造物質(zhì)財富，那么我不得不告訴你--梅森素數沒(méi)有什么用處，多知道一個(gè)非常大的素數似乎也沒(méi)什么用處。即使我們知道了一個(gè)無(wú)比巨大的梅森素數，也不會(huì )使我們的錢(qián)包增加一分錢(qián)（嗨等一等！如果你只對錢(qián)感興趣的話(huà)，也請不要立刻撇下我的文章。我其實(shí)是說(shuō)，我上面說(shuō)的話(huà)要排除我在這篇文章題目中提到的那十萬(wàn)美元的獎金--你的錢(qián)包也許會(huì )因此鼓起來(lái)的。所以請耐心一點(diǎn)）。

　　但是人類(lèi)并不只需要物質(zhì)財富。博物館里的鉆石有什么用場(chǎng)呢？為什么人類(lèi)要收集它們？因為它們美麗而稀少。作為人類(lèi)智慧的結晶，素數、梅森素數和與它密切相關(guān)的完美數是非常美麗的。它們的定義簡(jiǎn)單，卻又如此神秘莫測，象歐幾里德、笛卡爾、費爾馬、萊布尼茲、歐拉這樣的偉大數學(xué)家都因為它們的美麗而對它作過(guò)大量研究；大家也看到，兩千多年來(lái)，經(jīng)過(guò)無(wú)數代人的辛勤工作，我們一共只收集到38個(gè)梅森素數，它們是非常稀少的。對于數學(xué)家來(lái)說(shuō)，搜集素數、梅森素數和完美數是和收集鉆石一樣富有樂(lè )趣的事情。

　　人類(lèi)還需要榮耀--也許更勝于財富。在體育運動(dòng)中，能夠跑得更快一點(diǎn)，跳得更高一點(diǎn)，難道真的有實(shí)際物質(zhì)方面的用途嗎？不，我們喜歡接受挑戰，我們希望能贏(yíng)。打破一個(gè)體育世界記錄，攀登珠穆朗瑪峰，駕船橫穿太平洋……，那是對人類(lèi)體能極限的挑戰；而尋找更大的素數，則是一項對人類(lèi)智慧的挑戰。當我們完成了一項前所未有的任務(wù)時(shí)，我們總會(huì )感到無(wú)比驕傲。1963年，當第23個(gè)梅森素數被找到時(shí)，發(fā)現它的美國伊利諾斯大學(xué)數學(xué)系是如此地驕傲，以致于把所有從系里發(fā)出的信件都敲上了"211213-1是個(gè)素數"的郵戳。

　　在歐拉證明M_31是素數以后，下一個(gè)最大素數的記錄由蘭德里(Landry)于1867年獲得：M_59/179951=3203431780337。這不是一個(gè)梅森素數。這個(gè)記錄保持了九年。

　　1876年愛(ài)德華·盧卡斯使用了一個(gè)比費爾馬和歐拉的方法更先進(jìn)的手段，證明了M_127是一個(gè)素數。這個(gè)記錄保持了七十五年。直到費里葉(Ferrier)于1951年使用一部手搖計算機證明了(2148+1)/17是一個(gè)素數，它有41位數。

　　借助手搖計算機的方法要算作手工計算方法還是要算做計算機方法，大概是可以探討的問(wèn)題。不過(guò)技術(shù)的發(fā)展一下子把這種爭論變得毫無(wú)必要。值得指出的是，在人類(lèi)尋找大素數的旅途中，數學(xué)理論的改善要遠遠比具有強大堅韌的計算能力重要得多。盧卡斯的方法在1930年被勒梅(Lehmer)簡(jiǎn)化后，盧卡斯-勒梅測試成為現在尋找梅森素數的標準方法。

　�。ūR卡斯-勒梅測試：對于所有大于1的奇數p，M_p是素數當且僅當M_p整除S(p-1)，其中S(n)由S(n+1)=S(n)2-2，S(1)=4遞歸定義。這個(gè)測試尤其適合于計算機運算，因為除以M_p=2p-1的運算在二進(jìn)制下可以簡(jiǎn)單地用計算機特別擅長(cháng)的移位和加法操作來(lái)實(shí)現。判斷一個(gè)梅森數是素數的方法比判斷一個(gè)差不多大小的其他類(lèi)型數是素數的方法要簡(jiǎn)單得多，所以在尋找最大素數的過(guò)程中，大部分紀錄都是梅森素數。）

　　在1951年米勒和維勒(Miller & Wheeler)借助于EDSAC計算機（這種計算機還不如我們現在使用的一般計算器，它只有5K的內存）發(fā)現了長(cháng)達79位的素數180(M_127)2+1。這個(gè)記錄還是沒(méi)能保持多久。次年羅賓遜應用SWAC計算機，在1952年初發(fā)現了第13和第14號梅森素數：M_521和M_607，后面連續三個(gè)梅森素數也在同一年被陸續發(fā)現：M_1279，M_2203和M_2281。

　　在那以后的年代里，為了打破巨大素數紀錄而使用的計算機越來(lái)越強大，其中有著(zhù)名的IBM360型計算機，和超級計算機Cray系列。大家可以參看上面的梅森素數表來(lái)了解這個(gè)競賽過(guò)程。在此其間只有一次一個(gè)不是梅森素數的素數坐上過(guò)"已知最大素數"的寶座，它是39158*2216193-1，在1989年被發(fā)現。1996年發(fā)現的M_1257787是迄今為止最后一個(gè)由超級計算機發(fā)現的梅森素數，數學(xué)家使用了Cray T94。

　　然后，GIMPS的時(shí)代到來(lái)了。

　　四、GIMPS--互聯(lián)網(wǎng)梅森素數大搜索

　　1995年程序設計師喬治·沃特曼(George Woltman)開(kāi)始收集整理有關(guān)梅森素數計算的數據。他編制了一個(gè)梅森素數尋找程序并把它放在網(wǎng)頁(yè)上供數學(xué)愛(ài)好者免費使用。這就是"互聯(lián)網(wǎng)梅森素數大搜索"計劃(GIMPS，the Great Internet Mersenne Prime Search)。在這個(gè)計劃中，十幾位數學(xué)專(zhuān)家和幾千名數學(xué)愛(ài)好者正在尋找下一個(gè)最大的梅森素數，并且檢查以前梅森素數紀錄之間未被探索的空隙。比如上面的梅森素數表中，最后那個(gè)素數的序號是未知的，我們不知道第37號梅森素數和它之間是否還存在著(zhù)其他未被發(fā)現的梅森素數。

　　1997年斯科特·庫爾沃斯基(Scott Kurowski)和其他人建立了"素數網(wǎng)"(PrimeNet)，使分配搜索區間和向GIMPS發(fā)送報告自動(dòng)化�，F在只要你去GIMPS的主頁(yè)下載那個(gè)免費程序，你就可以立刻參加GIMPS計劃搜尋梅森素數。幾乎所有的常用計算機平臺都有可用的版本。程序以最低的優(yōu)先度在你的計算機上運行，所以對你平時(shí)正常地使用計算機幾乎沒(méi)有影響。程序也可以隨時(shí)被停止，下一次啟動(dòng)時(shí)它將從停止的地方繼續進(jìn)行計算。

　　從1996年到1998年，GIMPS計劃發(fā)現了三個(gè)梅森素數：M_1398269、M_2976221和M_3021377，都是使用奔騰型計算機得到的結果。

　　1999年3月，在互聯(lián)網(wǎng)上活動(dòng)的一個(gè)協(xié)會(huì )"電子邊界基金"(EFF，Electronic Frontier Foundation)宣布了由一位匿名者資助的為尋找巨大素數而設立的獎金。它規定向第一個(gè)找到超過(guò)一百萬(wàn)位的素數的個(gè)人或機構頒發(fā)五萬(wàn)美元的獎金，這就是我們最一開(kāi)始說(shuō)到的哈吉拉特瓦拉得到的獎金。后面的獎金依次為：超過(guò)一千萬(wàn)位，十萬(wàn)美元；超過(guò)一億位，十五萬(wàn)美元；超過(guò)十億位，二十五萬(wàn)美元。

　　搜尋結果的驗證和獎金的頒發(fā)是非常嚴格的。比如說(shuō)，得到的結果必須是顯式的--你不能宣稱(chēng)你的結果是一個(gè)有一百個(gè)方程組成的方程組的解，卻不把它解出來(lái)。結果必須由另一臺計算機獨立驗證。所有這些規則都在EFF網(wǎng)站上進(jìn)行了解釋。

　　應該指出的是，通過(guò)參加GIMPS計劃來(lái)獲得獎金的希望是相當小的。哈吉拉特瓦拉使用的計算機是當時(shí)21000臺計算機中的一臺。每一個(gè)參與者都在驗證分配給他的不同梅森數，當然其中絕大多數都不是素數--他只有大約三萬(wàn)分之一的可能性碰到一個(gè)素數。

　　下一個(gè)十萬(wàn)美元的獎金將被頒發(fā)給第一個(gè)找到超過(guò)一千萬(wàn)位的素數的個(gè)人或機構。這一次的計算量將大約相當于上一次的125倍�，F在GIMPS得到的計算能力為每秒7000億次浮點(diǎn)運算，和一臺當今最先進(jìn)的超級矢量計算機，比如Cray T932的運行能力相當。但是如果GIMPS要使用這樣的超級計算機，一天就需要支付大約二十萬(wàn)美元。而現在他們需要的費用，只不過(guò)是支持網(wǎng)站運行的費用，和總共幾十萬(wàn)美元的獎金罷了。

　　五、網(wǎng)上分布式計算計劃

　　GIMPS只不過(guò)是互聯(lián)網(wǎng)上眾多的分布式計算計劃中的一個(gè)罷了，GIMPS主頁(yè)上就有這些計劃的介紹。

　　分布式計算是一門(mén)計算機學(xué)科，它研究如何把一個(gè)需要非常巨大的計算能力才能解決的問(wèn)題分成許多小的部分，然后把這些部分分配給許多計算機進(jìn)行處理，最后把這些計算結果綜合起來(lái)得到最終的結果。有時(shí)侯計算量是如此之大，需要全世界成千上萬(wàn)甚至更多臺計算機一起工作，才能在合乎情理的時(shí)間內得到結果。GIMPS計劃就是在進(jìn)行這樣的分布式計算。

　　但它并不是最著(zhù)名的分布式計算計劃。致力于尋找宇宙中智慧生命的"搜尋地外文明計劃"(SETI計劃)中的SETI@HOME工程，已在全世界招募了290萬(wàn)名(!)志愿者，利用屏幕保護程序來(lái)處理射電望遠鏡接受到的大量的宇宙間傳來(lái)的無(wú)線(xiàn)電信號。如果你參加這個(gè)計劃，也許有一天會(huì )在你的計算機上破譯出外星人發(fā)來(lái)的問(wèn)候呢。

　　你也可以用你的計算機空余的計算能力為人類(lèi)征服癌癥作出貢獻。英國科學(xué)家設計了類(lèi)似SETI@HOME工程的分布式計算屏保，它從有關(guān)網(wǎng)站下載數據，分析化學(xué)物質(zhì)分子的抗癌性能，然后將分析結果通過(guò)互聯(lián)網(wǎng)傳回給研究人員，作為研制新型抗癌藥物的參考。這項工程將于2001年4月3日在美國加利福尼亞州正式啟動(dòng)。

　　計算機硬件的更新令人目不暇接，上半年買(mǎi)的最新式的個(gè)人電腦，在下半年就變成了大路貨。三四年前的CPU，現在變得一錢(qián)不值--也許不能這么說(shuō)，你根本就買(mǎi)不到它們了--市面上最便宜的CPU也要比它們強大得多。而一臺普通的家用計算機連續運轉五年也是沒(méi)有問(wèn)題的。所以，對待計算機的最經(jīng)濟的態(tài)度就是：讓它運轉。

　　而人類(lèi)還有那么多的東西需要計算，還有那么多的問(wèn)題需要找到回答，還有那么多的難關(guān)需要克服。我們需要越來(lái)越巨大的計算能力，我們也擁有這樣的計算能力，只是太多太多被白白地閑置浪費掉了�；ヂ�(lián)網(wǎng)已經(jīng)使大規模的分布式計算計劃成為可能�，F在，我們唯一需要的，就是這個(gè)網(wǎng)上每一個(gè)結點(diǎn)上計算機用戶(hù)的意愿和信心了。

　　全世界的計算機聯(lián)合起來(lái)！