已知最大質數

本页使用了标题或全文手工转换
维基百科,自由的百科全书
電子電腦發明後已知最大質數數位的按年圖表,至2016年為止。垂直刻度為對數尺度,紅線為曲線擬合y = exp(0.187394 t − 360.527),t為年份

已知最大質數(截至2021年9月 (2021-09))為282,589,933 − 1,十進制時有24,862,048位數,由互联网梅森素数大搜索GIMPS)的志願者派翠克·拉羅次(Patrick Laroche)於2018年發現[1]

質數,又名素数,是一個除1與自身之外沒有其他因數正整数欧几里得定理說明質數沒有上限,不少數學家與嗜好者故一直尋找大質數。

不少大質數為梅森素数,定義為2的冪減去1的正整數。截至2018年12月 (2018-12),首八個已知大質數皆為梅森素数[2]。近十七次最大質數紀錄皆為梅森素数[3][4]。所有梅森素数的二进制表示中,所有數字皆為1[5]

卢卡斯-莱默检验法快速傅里叶变换比起其他方式能更快速尋找到梅森素数

現時紀錄

已知最大質數為282,589,933 − 1,共有24,862,048位數,由互联网梅森素数大搜索於2018年12月發現[1]。其數值為:

148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ...

(省略24,861,808位數)

... 062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591[6]

上面只顯示首尾各120位數。

獎金

互联网梅森素数大搜索現為下載其軟件並成功尋找新梅森素数的參與者提供3,000美元獎金,該梅森素数的數位應少於一億位。

电子前哨基金会亦為大質數的找尋設立了數個獎項[7],互联网梅森素数大搜索亦有協調一億數位以上的質數搜索,並與成功尋找者分享电子前哨基金会所提供的150,000元美金獎金。

1999年發現首個超過一百萬數位的質數,並取得50,000美元獎金[8]。2008年發現了超過一千萬數位的質數,並取得100,000美元獎金[7]時代雜誌稱之為2008年第29名最佳發現[9]兩項獎金皆為互联网梅森素数大搜索的參加者。电子前哨基金会現為首個一億及十億數位的質數提供獎金[7]

已知最大質數歷史

下表列出已知最大質數沿革,並按時序排列[3]。此處Mn = 2n − 1,為2的n次方。時間最長的紀錄保持者為M19 = 524,287,為已知最大質數共計144年。1456年之前未存有關最大質數的紀錄。

數字 數字展開
(僅限小於M5000的數字)
數位 發現年份 發現者
M13 8,191 4 1456 佚名
M17 131,071 6 1588 伯多祿·卡塔迪
M19 524,287 6 1588 伯多祿·卡塔迪
6,700,417 7 1732 萊昂哈德·歐拉
歐拉並未正式發表此數,但他於232 + 1的因式分解中已完成此質數的大部分證明過程,故部分專家認為歐拉知道此為質數[10]
M31 2147483647 10 1772 萊昂哈德·歐拉
67,280,421,310,721 14 1855 湯馬斯·克勞森英语Thomas Clausen (mathematician)
M127 170,141,183,460,469,231,731,687,303,715,884,105,727 39 1876 爱德华·卢卡斯
20,988,936,657,440,586,486,151,264,256,610,222,593,863,921 44 1951 Aimé Ferrier
使用機械計算機發現,非使用電腦發現的最大質數
180×(M127)2+1 5210644015679228794060694325390955853335898483908056458352183851018372555735221 79 1951 J. C. P.米勒英语J. C. P. Miller大衛·惠勒英语David Wheeler (computer scientist)[11]
使用劍橋大學英语University of Cambridge Mathematical LaboratoryEDSAC電腦
M521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 157 1952
M607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 183 1952
M1279 104079321946...703168729087 386 1952
M2203 147597991521...686697771007 664 1952
M2281 446087557183...418132836351 687 1952
M3217 259117086013...362909315071 969 1957
M4423 285542542228...902608580607 1,332 1961
M9689 478220278805...826225754111 2,917 1963
M9941 346088282490...883789463551 2,993 1963
M11213 281411201369...087696392191 3,376 1963
M19937 431542479738...030968041471 6,002 1971
M21701 448679166119...353511882751 6,533 1978
M23209 402874115778...523779264511 6,987 1979
M44497 13,395 1979 854509824303...961011228671
M86243 25,962 1982 536927995502...709433438207
M132049 39,751 1983
M216091 65,050 1985
391581×2216193−1 65,087 1989 群組發現,包括約翰·布朗、藍登·克特·諾爾英语Landon Curt Noll、B. K. 柏拉狄、哲恩·史密夫、喬爾·史密夫、沙治奧[12][13],為已知最大質數歷史中最大的非梅森素數。
M756839 227,832 1992
M859433 258,716 1994
M1257787 378,632 1996
M1398269 420,921 1996 互联网梅森素数大搜索,喬爾·阿孟較得
M2976221 895,932 1997 互联网梅森素数大搜索,戈登·斯彭斯
M3021377 909,526 1998 互联网梅森素数大搜索,羅蘭·克拉克森
M6972593 2,098,960 1999 互联网梅森素数大搜索,拿恩·哈拉華拉
M13466917 4,053,946 2001 互联网梅森素数大搜索,米高·卡梅倫
M20996011 6,320,430 2003 互联网梅森素数大搜索,米高·沙夫
M24036583 7,235,733 2004 互联网梅森素数大搜索,喬許·芬德利
M25964951 7,816,230 2005 互联网梅森素数大搜索,馬田·諾或
M30402457 9,152,052 2005 互联网梅森素数大搜索柯蒂斯·库珀與史提夫·布恩
M32582657 9,808,358 2006 互联网梅森素数大搜索柯蒂斯·库珀與史提夫·布恩
M43112609 12,978,189 2008 互联网梅森素数大搜索,埃德森·史密夫
M57885161 17,425,170 2013 互联网梅森素数大搜索柯蒂斯·库珀
M74207281 22,338,618 2016 互联网梅森素数大搜索柯蒂斯·库珀
M77232917 23,249,425 2017 互联网梅森素数大搜索,強納森·佩斯
M82589933 24,862,048 2018 互联网梅森素数大搜索,派翠克·拉羅次

互联网梅森素数大搜索發現了近十五個最大質數紀錄。

二十大已知質數

克里斯·科德韋爾設有一列表,內共有已知最大的五千個質數[14][15],其中最大二十個列於下表。

排名 數字 發現日期 數位 參考資料
1 282589933 − 1 2018-12-07 24,862,048 [1]
2 277232917 − 1 2017-12-26 23,249,425 [16]
3 274207281 − 1 2016-01-07 22,338,618 [17]
4 257885161 − 1 2013-01-25 17,425,170 [18]
5 243112609 − 1 2008-08-23 12,978,189 [19]
6 242643801 − 1 2009-06-04 12,837,064 [20]
7 237156667 − 1 2008-09-06 11,185,272 [19]
8 232582657 − 1 2006-09-04 9,808,358 [21]
9 10223 × 231172165 + 1 2016-10-31 9,383,761 [22]
10 230402457 − 1 2005-12-15 9,152,052 [23]
11 225964951 − 1 2005-02-18 7,816,230 [24]
12 224036583 − 1 2004-05-15 7,235,733 [25]
13 220996011 − 1 2003-11-17 6,320,430 [26]
14 10590941048576 + 1 2018-10-31 6,317,602 [27]
15 9194441048576 + 1 2017-08-29 6,253,210 [28]
16 168451 × 219375200 + 1 2017-09-17 5,832,522 [29]
17 1234471048576 − 123447524288 + 1 2017-02-23 5,338,805 [30]
18 7 × 66772401 + 1 2019-09-09 5,269,954 [31]
19 8508301 × 217016603 − 1 2018-03-21 5,122,515 [32]
20 6962 × 312863120 − 1 2020-02-29 4,269,952 [33]

參見

參考資料

  1. ^ 1.0 1.1 1.2 GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1. Mersenne Research, Inc. 2018-12-21 [2018-12-21]. (原始内容存档于2020-08-15). 
  2. ^ Caldwell, Chris. The largest known primes - Database Search Output. Prime Pages. [2018-06-03]. (原始内容存档于2021-03-12). 
  3. ^ 3.0 3.1 Caldwell, Chris. The Largest Known Prime by Year: A Brief History. Prime Pages. [2016-01-20]. (原始内容存档于2013-08-19). 
  4. ^ 最後一個非梅森素数為391,581 ⋅ 2216,193 − 1页面存档备份,存于互联网档案馆);參見The Largest Known Prime by Year: A Brief History页面存档备份,存于互联网档案馆),Caldwell着
  5. ^ Perfect Numbers. Penn State University. [2019-10-06]. (原始内容存档于2020-08-03). An interesting side note is about the binary representations of those numbers... 
  6. ^ 存档副本. [2020-07-30]. (原始内容存档于2020-08-15). 
  7. ^ 7.0 7.1 7.2 Record 12-Million-Digit Prime Number Nets $100,000 Prize. Electronic Frontier Foundation. 电子前哨基金会. 2009-10-14 [2011-11-26]. (原始内容存档于2011-08-05). 
  8. ^ Electronic Frontier Foundation, Big Prime Nets Big Prize页面存档备份,存于互联网档案馆).
  9. ^ Best Inventions of 2008 - 29. The 46th Mersenne Prime. Time (时代公司). 2008-10-29 [2012-01-17]. (原始内容存档于2013-08-22). 
  10. ^ C. Edward Sandifer. How Euler Did Even More. 2007-08-30: 43 [2020-07-30]. ISBN 0883855844. (原始内容存档于2020-08-04). 
  11. ^ J. Miller英语J. C. P. Miller, Large Prime Numbers. Nature 168, 838 (1951).
  12. ^ Letters to the Editor页面存档备份,存于互联网档案馆). The American Mathematical Monthly 97, no. 3 (1990), p. 214. Accessed May 22, 2020.
  13. ^ Proof-code: Z页面存档备份,存于互联网档案馆), The Prime Pages英语Prime Pages.
  14. ^ The Prime Database: The List of Largest Known Primes Home Page. primes.utm.edu/primes. Chris K. Caldwell. [2017-09-30]. (原始内容存档于2021-02-27). 
  15. ^ The Top Twenty: Largest Known Primes. Chris K. Caldwell. [2018-01-03]. (原始内容存档于2021-02-25). 
  16. ^ GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1. mersenne.org. 互联网梅森素数大搜索. [2018-01-03]. (原始内容存档于2018-01-03). 
  17. ^ GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1. mersenne.org. 互联网梅森素数大搜索. [2017-09-29]. (原始内容存档于2018-01-07). 
  18. ^ GIMPS Discovers 48th Mersenne Prime, 257,885,161-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2013-02-05 [2017-09-29]. (原始内容存档于2021-01-26). 
  19. ^ 19.0 19.1 GIMPS Discovers 45th and 46th Mersenne Primes, 243,112,609-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2008-09-15 [2017-09-29]. (原始内容存档于2011-06-03). 
  20. ^ GIMPS Discovers 47th Mersenne Prime, 242,643,801-1 is newest, but not the largest, known Mersenne Prime.. mersenne.org. 互联网梅森素数大搜索. 2009-04-12 [2017-09-29]. (原始内容存档于2021-02-19). 
  21. ^ GIMPS Discovers 44th Mersenne Prime, 232,582,657-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2006-09-11 [2017-09-29]. (原始内容存档于2021-01-26). 
  22. ^ PrimeGrid's Seventeen or Bust Subproject (PDF). primegrid.com. PrimeGrid英语PrimeGrid. [2017-09-30]. (原始内容存档 (PDF)于2021-01-15). 
  23. ^ GIMPS Discovers 43rd Mersenne Prime, 230,402,457-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2005-12-24 [2017-09-29]. (原始内容存档于2021-03-14). 
  24. ^ GIMPS Discovers 42nd Mersenne Prime, 225,964,951-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2005-02-27 [2017-09-29]. (原始内容存档于2021-03-14). 
  25. ^ GIMPS Discovers 41st Mersenne Prime, 224,036,583-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2004-05-28 [2017-09-29]. (原始内容存档于2021-01-29). 
  26. ^ GIMPS Discovers 40th Mersenne Prime, 220,996,011-1 is now the Largest Known Prime.. mersenne.org. 互联网梅森素数大搜索. 2003-12-02 [2017-09-29]. (原始内容存档于2020-06-07). 
  27. ^ PrimeGrid's Generalized Fermat Prime Search (PDF). primegrid.com. PrimeGrid英语PrimeGrid. [2018-11-07]. (原始内容存档 (PDF)于2021-01-15). 
  28. ^ PrimeGrid's Generalized Fermat Prime Search (PDF). primegrid.com. PrimeGrid英语PrimeGrid. [2017-09-29]. (原始内容存档 (PDF)于2021-02-26). 
  29. ^ PrimeGrid's Prime Sierpinski Problem (PDF). primegrid.com. PrimeGrid英语PrimeGrid. [2017-09-29]. (原始内容存档 (PDF)于2020-12-23). 
  30. ^ The Prime Database: Phi(3,-123447^524288). primes.utm.edu. The Prime Pages. [2017-09-30]. (原始内容存档于2021-01-21). 
  31. ^ The Prime Database: 7*6^6772401+1. primes.utm.edu. The Prime Pages. [2019-09-12]. (原始内容存档于2021-01-21). 
  32. ^ PrimeGrid's Woodall Prime Search (PDF). primegrid.com. PrimeGrid英语PrimeGrid. [2018-04-02]. (原始内容存档 (PDF)于2021-01-21). 
  33. ^ The Prime Database: 6962*31^2863120-1. primes.utm.edu. The Prime Pages. [2020-04-06]. (原始内容存档于2021-01-21). 

外部連結