ja.wikipedia.org

巨大な素数の一覧 - Wikipedia

  • ️Sun Nov 11 2012

出典: フリー百科事典『ウィキペディア（Wikipedia）』

『巨大な素数の一覧』（きょだいなそすうのいちらん、英: The List of Largest Known Primes）とは、アメリカの数学者クリス・カルドウェル（Chris Caldwell）が管理するウェブサイト「The PrimePages」[※ 1]にて公開されている、現在知られている中で最大の素数の上位ランキングを記した一覧である。

2024年10月の時点で「素数として確認された最大の数」は 2136,279,841 − 1 である。この素数は41,024,320 桁の長さを持ち、2024年10月12日に Great Internet Mersenne Prime Search (GIMPS) によって発表された[1]。

電子計算機の出現以降、知られている最大の素数の桁数が月日と共に増加していく様子を表したグラフ。縦軸は対数スケールである。赤線は経過年数 t の指数関数 y = exp(0.187394t − 360.527) による近似曲線。

ユークリッドにより素数が無数に存在することが証明されて以来、多くの数学者やアマチュア愛好家によってより大きな素数の探索が行われてきた。

発見済みの巨大な素数の多くがメルセンヌ数に属する。2024年10月現在までに発見された素数の大きさを比べると、上位7位までを全てメルセンヌ素数が占め、8位に初めてメルセンヌ数ではない素数が入る[2]。

メルセンヌ数の素数判定を行うリュカ-レーマー・テストでは、高速フーリエ変換を応用した効率的な実装を計算機上で利用することが可能であるため、メルセンヌ数以外の素数判定よりも速度の上で有利という事情がある。

2024年10月時点で素数であることが確認されている最大の数は 2136,279,841 − 1 で表される数で、十進法表示では 41,024,320 桁の数である。この素数は2024年に GIMPS により発見された[1]。

Great Internet Mersenne Prime Search (GIMPS) では、彼らの無料ソフトウェアを入手し計算機上で実行してくれる参加者が、1億桁未満のメルセンヌ素数のいずれかを発見する毎に、3000米ドルの懸賞金を渡すと提示している。

電子フロンティア財団 (EFF (英語版) ) では大きな素数の新記録に対する懸賞金を何部門か提示している[3]。1億桁以上の素数を最初に発見した者に与えられる予定の電子フロンティア財団からの懸賞金150,000米ドルに対し、GIMPS では賞金を参加者と分配する方向で調整中である。

100万桁を越える素数が1999年に発見されたときの懸賞金は50,000米ドルであった[4]。1000万桁を超える素数が2008年に発見されたときの懸賞金は100,000米ドルであり、さらに電子フロンティア財団からCooperative Computing Award (英語版) 賞が授与された[3]。この業績は Time 誌が選ぶ「2008年 Top Invention」の29番目として紹介された[5]。1億桁を越える素数の発見と10億桁を超える素数の発見に対する懸賞金はまだ提示されたままである[3]。ちなみに50,000米ドルと100,000米ドルの懸賞金の受賞者は両方ともGIMPSの参加者である。

以下の表は、時代と共に次々と大きな素数が発見されてきた経緯を時系列で示したものである[6]。ここでは Mn = 2n − 1 は指数 n のメルセンヌ数とする。「発見された中で最大の素数」としての扱いを受けた最長期間記録の素数は、M19 の 524,287 である。この素数は144年間にわたって「最大の素数」の座を守り続けた。ただし、1456年以前の最長記録は不明。

素数の式 十進法表記
（50桁まで） 		桁数 発見された年 備考
(巨大なメルセンヌ素数の発見経緯に関してはメルセンヌ数を参照)
11 11 2 ～紀元前1650年 古代エジプト人(Rhied Papyrus)（議論）[7]
7 7 1 ～紀元前400年 フィロラオスにより 7 は素数と認識されていた[8]。
127 127 3 ～紀元前300年 ユークリッドにより 127 と 89 は素数と認識されていた[9][10]。
M13 8,191 4 1456年 発見者不明
M17 131,071 6 1460年 発見者不明
M19 524,287 6 1588年 ピエトロ・カタルディ（英語版）が発見
{\displaystyle {\tfrac {2^{32}+1}{641}}} 6,700,417 7 1732年 レオンハルト・オイラーが発見
M31 2,147,483,647 10 1772年 レオンハルト・オイラーが発見
{\displaystyle {\tfrac {2^{64}+1}{274177}}} 67,280,421,310,721 14 1855年 トーマス・クラウゼンが発見
M127 [数値 1] 39 1876年 エドゥアール・リュカが発見
（手計算で素数であることが確かめられた最大の素数）
{\displaystyle {\tfrac {2^{148}+1}{17}}} [数値 2] 44 1951年 Aimé Ferrierが発見
（電子計算機を用いずに導かれた最大の素数）
180 × (M127)2 + 1 79 1951年 ケンブリッジ大学の電子計算機 EDSAC を使用
M521 157 1952年
M607 183 1952年
M1279 386 1952年
M2203 664 1952年
M2281 687 1952年
M3217 969 1957年
M4423 1,332 1961年
M9689 2,917 1963年
M9941 2,993 1963年
M11213 3,376 1963年
M19937 6,002 1971年 米国のブライアント・タッカーマン博士がIBM360/91型コンピュータで39分26秒4かけて計算[11]
M21701 6,533 1978年
M23209 6,987 1979年
M44497 13,395 1979年 カリフォルニア大学ローレンス・リバモア研究所でクレイ・ワン・コンピュータを2か月使って計算[12]
M86243 25,962 1982年
M132049 39,751 1983年
M216091 65,050 1985年 シェブロン・ジオサイエンセス社がCray X-MP/24コンピュータを使って計算[13]
391581 × 2216193 − 1 65,087 1989年
M756839 227,832 1992年 英国オクソンのAEAテクノロジーズ・ハーウェル研究所でCRAY-2スーパーコンピュータを使って計算[14]
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年
M136279841 41,024,320 2024年
  • 横軸：西暦
  • 縦軸：桁数の対数スケール
  • 赤：円周率近似値の桁数
  • 緑：最大素数の桁数
順位 素数 発見日 桁数 出典 備考
1 2136279841 − 1 2024年10月12日 41,024,320 [1]
2 282589933 − 1 2018年12月7日 24,862,048 [15]
3 277232917 − 1 2017年12月26日 23,249,425 [16]
4 274207281 − 1 2016年1月7日 22,338,618 [17]
5 257885161 − 1 2013年1月25日 17,425,170 [18]
6 243112609 − 1 2008年8月23日 12,978,189 [19]
7 242643801 − 1 2009年4月12日 12,837,064 [20]
8 5166932097152 − 5166931048576 + 1 2023年10月2日 11,981,518 [21] Mn 以外の式による、最大の素数
9 4658592097152 − 4658591048576 + 1 2023年5月31日 11,887,192 [22]
10 237156667 − 1 2008年9月6日 11,185,272 [19]
11 232582657 − 1 2006年9月4日 9,808,358 [23]
12 10223 × 231172165 + 1 2016年10月31日 9,383,761 [24]
13 230402457 − 1 2005年12月15日 9,152,052 [25]
14 4 × 511786358 + 1 2024年10月1日 8,238,312 [26]
15 225964951 − 1 2005年2月18日 7,816,230 [27]
16 69 × 224612729 − 1 2024年8月13日 7,409,172 [28]
17 224036583 − 1 2004年5月15日 7,235,733 [29]
18 107347 × 223427517 − 1 2024年8月4日 7,052,391 [30]
19 38432361048576 + 1 2024年12月17日 6,904,556 [31][32]
20 3 × 222103376 − 1 2024年9月30日 6,653,780 [33][32]
  • PrimeGrid（探索対象：ウッダル数、カレン数、その他）
  • GIMPS（探索対象：メルセンヌ数）
  • Riesel Sieve（終了）（探索対象：リーゼル数に伴う素数）
  1. ^ 170,141,183,460,469,231,731,687,303,715,884,105,727
  2. ^ 20,988,936,657,440,586,486,151,264,256,610,222,593,863,921
  1. ^ a b c “GIMPS Discovers Largest Known Prime Number: 2136,279,841-1”. GIMPS. 2025年3月13日閲覧。
  2. ^ “PrimePage Primes: Database Search Output”. PrimePages. 2025年3月13日閲覧。
  3. ^ a b c “Record 12-Million-Digit Prime Number Nets $100,000 Prize”. Electronic Frontier Foundation. Electronic Frontier Foundation (2009年10月14日). 2011年11月26日閲覧。
  4. ^ Electronic Frontier Foundation, Big Prime Nets Big Prize.
  5. ^ “Best Inventions of 2008 - 29. The 46th Mersenne Prime”. Time (Time Inc). (2008年10月29日) 2012年1月17日閲覧。
  6. ^ “The Largest Known Prime by Year: A Brief History”. Prime Pages. 2016年1月20日閲覧。
  7. ^ There is no mentioning among the en:ancient Egyptians of prime numbers, and they did not have any concept for prime numbers known today. In the en:Rhind papyrus (1650 BC) the Egyptian fraction expansions have fairly different forms for primes and composites, so it may be argued that they knew about prime numbers. "The Egyptians used ($) in the table above for the first primes r = 3, 5, 7, or 11 (also for r = 23). Here is another intriguing observation: That the Egyptians stopped the use of ($) at 11 suggests they understood (at least some parts of) Eratosthenes's Sieve 2000 years before Eratosthenes 'discovered' it." The Rhind 2/n Table [Retrieved 2012-11-11].
  8. ^ Harris, Henry S (1999). The Reign of the Whirlwind. p. 252. hdl:10315/918.
  9. ^ Nicomachus' "Introduction to Arithmetic" translated by Martin Luther D'Ooge (p.52)
  10. ^ “Euclid's Elements, Book IX, Proposition 36”. 2016年12月5日閲覧。
  11. ^ ノリス・マクワーター, ed (1978). ギネスブック 世界記録事典 79年度版. 講談社. p. 116
  12. ^ ノリス・マクワーター, ed (1982). ギネスブック 82 世界記録事典. 大出健. 講談社. p. 121. ISBN 4-06-142667-2
  13. ^ アラン・ラッセル, ed (1986). ギネスブック'87 世界記録事典. 大出健. 講談社. p. 396. ISBN 4-06-202948-0
  14. ^ ピーター・マシューズ, ed (1992). ギネスブック'93. 講談社. p. 128. ISBN 4-88693-254-1
  15. ^ “GIMPS Discovers Largest Known Prime Number: 282,589,933-1”. GIMPS. 2025年3月13日閲覧。
  16. ^ “GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1”. GIMPS. 2025年3月13日閲覧。
  17. ^ “GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1”. GIMPS. 2025年3月13日閲覧。
  18. ^ “GIMPS Discovers 48th Mersenne Prime, 257,885,161-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  19. ^ a b “GIMPS Discovers 45th and 46th Mersenne Primes, 243,112,609-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  20. ^ “GIMPS Discovers 47th Mersenne Prime, 242,643,801-1 is newest, but not the largest, known Mersenne Prime.”. GIMPS. 2025年3月13日閲覧。
  21. ^ “PrimePage Primes: 5166932097152 - 5166931048576 + 1”. PrimePages. 2025年3月13日閲覧。
  22. ^ “PrimePage Primes: 4658592097152 - 4658591048576 + 1”. PrimePages. 2025年3月13日閲覧。
  23. ^ “GIMPS Discovers 44th Mersenne Prime, 232,582,657-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  24. ^ “PrimeGrid’s Seventeen or Bust Subproject” (PDF). PrimeGrid. 2025年3月13日閲覧。
  25. ^ “GIMPS Discovers 43rd Mersenne Prime, 230,402,457-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  26. ^ “PrimePage Primes: 4·511786358 + 1”. PrimePages. 2025年3月13日閲覧。
  27. ^ “GIMPS Discovers 42nd Mersenne Prime, 225,964,951-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  28. ^ “PrimePage Primes: 69·224612729 - 1”. PrimePages. 2025年3月13日閲覧。
  29. ^ “GIMPS Discovers 41st Mersenne Prime, 224,036,583-1 is now the Largest Known Prime.”. GIMPS. 2025年3月13日閲覧。
  30. ^ “PrimePage Primes: 107347·223427517 - 1”. PrimePages. 2025年3月13日閲覧。
  31. ^ “PrimePage Primes: 38432361048576 + 1”. PrimePages. 2025年3月13日閲覧。
  32. ^ a b “PrimeGrid Mega Primes”. PrimeGrid. 2025年3月13日閲覧。
  33. ^ “PrimePage Primes: 3·222103376 - 1”. PrimePages. 2025年3月13日閲覧。
数の例
表現法
表記
演算子
順序数階層
関連項目