梅森素數是什麼?

梅森素數是什麼?
最近

美国国家海洋和大气局(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 奔騰四處理器的電子計算機和五十天計算時間

找把它驗明正身。

法國數學家梅森 (Marin Mersenne 1588-1648) 和業餘數學王子費馬 (Pierre de Fermat 1601-1665) 是好友。

十七世紀

費馬也曾對完全數的問題有興趣

詳見本網另一文章《豐數、虧數和完全數》。

他也必然考察過形如 2p-1 的數的素性。

1640年 6月

費馬給梅森的信中提出三個定理

它們更是研究整數素性的基礎：1. 若 n 不是素數

則(2^n)-1 也不是素數。

2. 若 n 是素數

則(2^n)-2 可被 2n 整除

即 2(n-1)≡1 (mod n)

即後來的「費馬小定理」(Fermat Little Theorem)。

3. 若 n 是素數除了 2kn 1 這種形式的數以外

(2^n)-1 不能被其他形式的素數整除。

定理(1)相當於若(2^n)-1 是素數

則 n 是素數

反之則未必成立。

梅森在其於1644年出版的著作《物理—數學探索》的序言中提出在不超過 257的55個素數中

僅當 p=2、3、5、7、13、17、19、31、67、127和257

這11個素數時

(2^p)-1 為素數。

他本人驗証了前七個數

後四個數因計自算量太大而未能驗証。

為了紀念他

後人把形如 2p-1 的數稱為梅森數(Mp)

形如 (2^p)-1 的素數稱為梅森素數 (Mersenne Prime)

上述斷言稱為梅森猜想。

分數|進位法|向量|方程式|多項式|雙曲線|不等式|對角線|數獨|矩陣|統計學|內角和|機率|體積換算|小數|三角函數|圓周率|負數|因數|長度換算|幾何|複數|質數|心算|等比級數|拋物線|面積換算|證明題|平均數|開根號|商高定理|倍數|離散數學|微積分|畢氏定理|演算法|代數|分解式|