梅森素數大搜索[24 August,2005 1:09 ] @ 世盃決賽

梅森素數大搜索[24 August,2005 1:09 ]
最近，美國國家海洋和大氣局(NOAA)資訊技術顧問、數學愛好者喬希·芬德利使用一台裝有2.4GHz奔騰處理器的個人電腦，發現了目前世界上已知的最大素數。該素數為224036583－1(即2的24 036 583次方減1)，它有7 235 733位數，如果用普通字號將這個數字連續寫下來，它的長度可達3萬米!科學家們認為這項成果是數學研究和計算技術中最重要的突破之一。　　素數又稱質數，是在大於1的整數中只能被1和其自身整除的數(如2、3、5、7、11等)；素數有無窮多個。數學中形如2p－1(其中p為素數)的素數稱為梅森素數(Mersenne prime)；它是以17世紀法國數學家、法蘭西科學院奠基人馬林·梅森(Marin Mersenne)的姓氏命名的，因為他對這一特殊形式的素數做了大量的計算和驗證工作以及他在當時歐洲科學界有著崇高的學術地位。早在公元前300多年，古希腊數學家歐幾里得就開創了探索這一素數的先河，他在《幾何原本》這一經典著作中論述完美數時曾研究過2p－1型素數。不少著名數學家如費馬、笛卡爾、萊布尼玆、歐拉、哥德巴赫、魯卡斯、香吉斯、柯爾、吉里斯等也研究過這一素數。2000多年來，人類僅找到41個梅森素數；而近百年來，人們發現的已知最大素數幾乎都是梅森素數。梅森素數是數論研究中的一項重要內容，也是當今科學探索的熱點和難點。這類素數珍奇而迷人，因此被人們譽為“數海明珠”。　　梅森素數貌似簡單，而研究難度卻很大。它不僅需要高深的理論和純熟的技巧，而且需要進行艱巨的計算。1772年瑞士數學家歐拉在雙目失明的情況下，以驚人的毅力靠心算證明231－1(即2 147 483 647)是第8個梅森素數，該素數有10位數，堪稱當時世界上已知的最大素數；他因此獲得了“數學英雄”的美名。1963年9月6日晚上8點，當第23個梅森素數211213－1通過大型電腦發現時，美國廣播公司(ABC)中斷了正常的節目播放，以第一時間發布了這一重要消息；而發現這一素數的美國伊利諾伊大學數學系全體師生感到無比驕傲，以致於把所有從系里發出的信件都蓋上了“211213－1是個素數”的郵戳。尤其值得一提的是，中國數學家及語言學家周海中經過多年的研究，於1992年首先給出了梅森素數分布的精確表達式，為人們尋找梅森素數提供了方便；后來這一成果被國際數學界命名為“周氏猜測”。　　網格(Grid，也稱第三代因特網)的出現使尋找梅森素數的研究者如虎添翼。1996年美國數學家和程序設計師喬治·沃特曼編制了一個梅森素數尋找程序，並把它放在因特網上供數學家和數學愛好者免費使用；這就是著名的“因特網梅森素數大搜索”(GIMPS)項目。它有24萬台電腦聯網來進行網格計算(即分布式計算)，以尋找新的梅森素數。芬德利就是參加該項目的全球7萬5 000名志願者之一，他用了5 年的時間，於2004年5月15日發現了第41個梅森素數224036583－1，他還花費了兩周的時間來進行驗證；有關專家也證實了他的發現。第35、36、37、38、39和40個梅森素數也都是與“大搜索”因特網聯通的個人電腦發現的。不久前，國際電子新領域基金會(IEFF)宣布了由一位匿名者資助的為通過GLMPS項目來尋找新的更大的梅森素數而設立的獎金。它規定向第一個找到超過1 000萬位數的個人或機構頒發10萬美元。后面的獎金依次為：超過1億位數，15萬美元；超過10億位數，25萬美元。但據悉，絕大多數研究者參與該項目不是為了金錢而是出於樂趣、榮譽感和探索精神。
　　尋找梅森素數在當代具有十分豐富的理論意義和實用價值。它是發現已知最大素數的最有效的途徑；它推動了數學皇后——數論的發展，也促進了計算數學、程序設計技術、分布式計算技術、因特網技術以及密碼技術的發展。尋找梅森素數的方法還可用來測試電腦硬體運算是否正確。科學家們認為，對於梅森素數的研究能力如何，已在某種意義上標志著一個國家的科技水平。可以相信，梅森素數這顆數學海洋中的璀璨明珠正以其獨特的魅力，吸引著更多的有志者去尋找和研究。
作者:張文文章來源:(《科學時報》2004年6月11日) http://hk.geocities.com/goodprimes/CMersenne1.htm
法國數學家梅森 (Marin Mersenne 1588-1648) 和業餘數學王子費馬 (Pierre de Fermat 1601-1665) 是好友。十七世紀，費馬也曾對完全數的問題有興趣，詳見本網另一文章《豐數、虧數和完全數》。他也必然考察過形如 2p-1 的數的素性。1640年 6月，費馬給梅森的信中提出三個定理，它們更是研究整數素性的基礎：
1. 若 n 不是素數，則 2n-1 也不是素數。
2. 若 n 是素數，則 2n-2 可被 2n 整除，即 2n-1=1 (mod n)，即後來的「費馬小定理」(Fermat Little Theorem)。
3. 若 n 是素數除了 2kn+1 這種形式的數以外， 2n-1 不能被其他形式的素數整除。
定理(1)相當於若 2n-1 是素數，則 n 是素數，反之則未必成立。
梅森在其於1644年出版的著作《物理—數學探索》的序言中提出在不超過 257的55個素數中，僅當 p=2、3、5、7、13、17、19、31、67、127和257 ，這11個素數時， 2p-1 為素數。他本人驗證了前七個數，後四個數因計自算量太大而未能驗證。為了紀念他，後人把形如 2p-1 的數稱為梅森數(Mp)，形如 2p-1 的素數稱為梅森素數 (Mersenne Prime) ，上述斷言稱為梅森猜想。然而這位梅森在其論作中竟有五個錯誤之多。
首先在1883年，佩爾武申 (Ivan Mikheevich Pervusin 1829-1900) 發現M61是素數，梅森數漏了一個。
接而在1903年，美國數學家科爾 (Frank N. Cole 1821-1926) 發現M67是合數，而
267-1=193707721*761838257287。
跟後波爾斯 (R. E. Powers) 在1911和1914年，又證明了M89和M107是素數。1922年克拉依切克 ( M. Kraitchik) 發現了M257是一合數。梅森合共漏掉了三個素數和誤把兩個合數看成素數。
反之，歐拉 (Leonhard Euler 1707-1783) 在1772年證明M31是素數，為梅森素數研究打了一枝強心針。
我們現在的計算法是法國數學家呂卡 (Edouard Lucas 1842-1891) 在1877年奠定的，他在1876年證明了M127是素數，其中
M127=1701 41183 46046 92317 31687 30371 58841 05727 ，這是沒有利用電子電腦找到最大的梅森素數。呂卡斯的判斷法我們另有文章詳細介紹。
1952年，美國人雷默 (Derrick Henry Lehmer 1905-1991) 和魯賓遜 (Raphael M. Robinson 1911-1994) 證明了 p=521、p=607、p=1279、p=2203 和 p=2281 五個梅森素數。
1958年，瑞典人黎塞爾 (Hans Riesel 1929- ) 和安德森 (A. Anderson) 指出 p=3217是梅森素數。
1962年，赫爾維茨 (Adolf Hurwitz 1859-1919)又發現 p=4253 和 p=4423 兩個梅森素數。
1964年，吉里斯 (Donald B. Gillies) 為研究梅森素數作了一大躍進，他找到了 p=9689 、 p=9941 和 p=11213 三個梅森素數。吉里斯更指出小於 X 的梅森素數個數等於 2 log log X / log 2 ，這也和梅森素數其他相關理論一樣，成了一個謎。
為記念梅森素數 p= 11213的發現而設計的郵印。
1971年，美國人塔克曼 (Bryant Tuckerman) 利用電子電腦的幫助，僅花了半小時，便發現了 p=19937 的梅森素數，和近300年前的梅森，花盡一生也計不了 p=257 ，可說是一大對比了。
1978年10月30日，十八歲的中學生尼克爾 (Laura Nickel) 和努爾 (Curt Noll)聯合發現了 p = 21701的梅森素數。翌年二月，努爾又單獨發現了 p = 23209 的梅森素數。電子電腦使尋找梅森素數的工作普及下去。
1979年4月8日，美國數學家斯洛溫斯基 (David Slowinski) 先後發現了四個梅森素數，分別是 p = 44497、 p = 86243 、p = 132049 和 p = 216091四個。那不過是 1979年至1985年六年內的事情而已。在1992年至1994年間，他和基治 (Paul Gage) 又找到第 32 至 34 個梅森素數，即 p = 756839、p = 859433 和 p = 1257787，合共找刑 7 個梅森素數之多，可謂一時無倆。
其後的五個梅森素數的發現都是借助 GIMPS (The Great Internet Mersenne Prime Search 大英特網梅森素數研究會) 的程式協助，法國人阿米格特 (Joel Armengaud) 於 1996 年找到第 35 個 p = 1398269 的梅森素數。一年後英國人史賓沙 (Gorden Spence) 發現第 36 個 p = 2976221 的梅森素數。1998年，當時年僅19歲的加州大學數學系學生克拉克森 (Roland Clarkson) 找到第 37 個 p = 3021377 的梅森素數。1999年僑居英國的日本人納揚 (Nayan Hajratwala) 找來了第 38 個 p = 6972593 的梅森素數，他參與 GIMPS 的計劃還得以其電子電腦運行 111 天才碰上這巨大素數。
美國人沃爾特曼 (George F. Woltman 1957- ) 和庫羅夫斯基 (Scott Kurowski)，是電子計算方面的專才。1996年其開始 GIMPS 的計劃，為尋找大素數提供程式上的支援。
之後，由於電子電腦的進一步普及和速度提昇，我們可以向更大的梅森素數進軍。直至現在，最大的梅森素數是在 2001年11月14日，由一位二十歲加拿大人卡麥隆 (Michael Cameron) 利用 GIMPS 的程式所發現的 213466917-1 ，這亦是現存最大的素數，是一個有 4053946 個數位的「龐然大物」，但這只不過是第 39 個梅森素數而已。他這發現更為他帶來了十萬美元的獎金，更成了當年 12月5日英國廣播公司科學版的頭條，右圖便是當時的內文插圖，可說是名利雙收了。
據悉，卡麥隆利用其配備的８００兆赫茲ＡＭＤ晶片的電腦加入到全球分布式計算網絡中，花費４５天的時間得到了這一結果。盡管這台電腦自身性能並不高，但由於分布式計算網絡連接了全球數十萬台電腦，這些電腦自身有富裕資源的時候就通過網絡進行運算，因此總的運算速度可達到每秒２萬億次，相當於一台超級電腦。
(照片取自「英國廣播公司科學版」http://news.bbc.co.uk/1/hi/sci/tech/1693364.stm
二零零三年十一月十七日，足足兩年之後，GIMPS 宣佈第四十個梅森素數已被發現，在同年十二月二日已被證明無誤。這正是 220996011-1 ，是一個長達 6320430 數位的素數。發現這素數的人正是沙法 (Micheal Shafer)，這是一名 26 歲的密芝根州立大學化學工程畢業生，義務協助梅森素數尋找工作。沙法利用密芝根州立大學的電腦和 GIMPS 沃爾特曼和庫羅夫斯基的程式聯上全球 211000台網絡電腦，跨時跨地的一同尋找這巨大素數，遇上了這大數以後他還也要花上 19 日才能驗證這新的梅森數的素性，結果當然是素數了。
這回可快一點了，在二零零四年五月十五日，差不多是發現第四十個梅森素數的半年之後，第四十一個梅森素數宣告被發現。這是 224036583-1 ，這回比上一個多了近一百萬個數位，達 7235733 個數位，正式跨越七百萬。發現者是芬迪尼 (Josh Fredley) ，他利用一台 2.4GHz 奔騰四處理器的電子電腦配以 GIMPS 的程式作了超過兩週的運算，才遇上這素數，接後的測試也用上了五天之久。
在二零零五年二月十八日，是上一個梅森素數被發現之後的九個月之後，第四十二個梅森素數宣告被發現。這是 225964951-1 ，一個有 7816230 個數位的龐然巨物，距千萬位又走前一步。這素數是由德國人諾華克醫生 (Martin Nowak) 發現的。諾華克是一名眼科醫生，工餘利用電腦尋找素數。我們可不要少看這素數，諾華克醫生在二月十八日找到它以前，也得用上一台 2.4GHz 奔騰四處理器的電子電腦和五十天計算時間，找把它驗明正身。來源：http://tw.knowledge.yahoo.com/question/?qid=1205071914561

.msgcontent .wsharing ul li { text-indent: 0; }

分享

Facebook
Plurk
YAHOO!

xytpuihehvxl

世盃決賽

xytpuihehvxl 發表在痞客邦留言(0) 人氣()

E-mail轉寄

世盃決賽

世盃決賽

梅森素數大搜索[24 August,2005 1:09 ]

歷史上的今天

留言列表

站方公告

活動快報

【全民...

我的好友

熱門文章

文章分類

最新文章

最新留言

動態訂閱

文章精選

文章搜尋

新聞交換(RSS)

誰來我家

參觀人氣

QR Code

POWERED BY