發表回覆

主題 通關密語 訪客發文, 請參考 這裡 輸入通關密語.

顯示表情符號

站內上傳圖檔     Upload.cc免費圖片上傳

數學塗鴉工具     常用數學符號表    

用Latex打數學方程式

 


 

+ / -檢視主題

[分享]費馬數

發表 J+W 於 星期五 十月 08, 2004 11:03 am

求知:搜尋費馬數因子

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個費馬素因子!

  加入這項搜索計劃,只需要下載有關程序。然后這個程序會以最低的優先度在計算機上運行,這對平時正常使用計算機幾乎沒有影響。如果你想利用計算機的空余時間做點有益的事情,還猶豫什麼?馬上行動起來,加入“費馬因子搜尋計劃”吧。你的微不足道的付出或許就能使你找到一個獨一無二的費馬素因子,從而使你在數學史上留下小小的一筆呢!

鏈接: http://www.fermatsearch.org/

原文網址:

http://www.equn.com/info/list.asp?id=21