巨大な素数の一覧
『巨大な素数の一覧』（きょだいなそすうのいちらん、英: The List of Largest Known Primes）とは、アメリカの数学者クリス・カルドウェル (Chris Caldwell) が管理するウェブサイト「The PrimePages」[※ 1]にて公開されている、現在知られている中で最大の素数の上位ランキングを記した一覧である。
2018年12月の時点で「素数として確認された最大の数」は 282,589,933 − 1 である。この素数は24,862,048 桁の長さを持ち、2018年12月に Great Internet Mersenne Prime Search (GIMPS) によって発見された。 [1]
ユークリッドにより素数が無数に存在することが証明されて以来、多くの数学者やアマチュア愛好家によってより大きな素数の探索が行われてきた。
発見済みの巨大な素数の多くがメルセンヌ数に属する。2018年12月現在までに発見された素数の大きさを比べると、上位8位までを全てメルセンヌ数が占め、9位に初めてメルセンヌ数ではない素数が入る[2]。
メルセンヌ数の素数判定を行うリュカ-レーマー・テストでは、高速フーリエ変換を応用した効率的な実装を計算機上で利用することが可能であるため、メルセンヌ数以外の素数判定よりも速度の上で有利という事情がある。
最大記録 編集
2018年12月時点で素数であることが確認されている最大の数は 282,589,933 − 1 で表される数で、十進法表示では 24,862,048 桁の数である。この素数は2018年に GIMPS により発見された[1]。この素数を印字すると
148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560… … (24,861,808 桁が省略されている) … …062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591
となる。
※ 上記は先頭と末尾それぞれ120桁のみの表示でしかない。
懸賞金 編集
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年 | ピエトロ・カタルディが発見 |
| 6,700,417 | 7 | 1732年 | レオンハルト・オイラーが発見 | |
| M31 | 2,147,483,647 | 10 | 1772年 | レオンハルト・オイラーが発見 |
| 67,280,421,310,721 | 14 | 1855年 | トーマス・クラウセンが発見 | |
| M127 | [数値 1] | 39 | 1876年 | エドゥアール・リュカが発見 （手計算で素数であることが確かめられた最大の素数） |
| [数値 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年 |
- 横軸：西暦
- 縦軸：桁数の対数スケール
- 赤：円周率近似値の桁数
- 緑：最大素数の桁数
上位20位の大きな素数 編集
| 順位 | 素数の式 | 発見日 | 桁数 |
|---|---|---|---|
| 1 | 282589933 − 1 | 2018年12月7日 | 24,862,048 |
| 2 | 277232917 − 1 | 2017年12月26日 | 23,249,425 |
| 3 | 274207281 − 1 | 2016年1月7日 | 22,338,618 |
| 4 | 257885161 − 1 | 2013年1月25日 | 17,425,170 |
| 5 | 243112609 − 1 | 2008年8月23日 | 12,978,189 |
| 6 | 242643801 − 1 | 2009年4月12日 | 12,837,064 |
| 7 | 237156667 − 1 | 2008年9月6日 | 11,185,272 |
| 8 | 232582657 − 1 | 2006年9月4日 | 9,808,358 |
| 9 | 10223 × 231172165 + 1 | 2016年11月6日 | 9,383,761 |
| 10 | 230402457 − 1 | 2005年12月15日 | 9,152,052 |
| 11 | 225964951 − 1 | 2005年2月18日 | 7,816,230 |
| 12 | 224036583 − 1 | 2004年5月15日 | 7,235,733 |
| 13 | 220996011 − 1 | 2003年11月17日 | 6,320,430 |
| 14 | 10590941048576 + 1 | 2018年10月31日 | 6,317,602 |
| 15 | 9194441048576 + 1 | 2017年8月29日 | 6,253,210 |
| 16 | 168451 × 219375200 + 1 | 2017年9月17日 | 5,832,522 |
| 17 | 1234471048576 − 123447524288 + 1 | 2017年2月23日 | 5,338,805 |
| 18 | 7 × 66772401 + 1 | 2019年9月9日 | 5,269,954 |
| 19 | 8508301 × 217016603 − 1 | 2018年3月21日 | 5,122,515 |
| 20 | 6962 × 312863120 − 1 | 2020年2月29日 | 4,269,952 |
素数探索の有力候補・手がかりに関する項目 編集
主な素数探索プロジェクト 編集
- PrimeGrid（探索対象：ウッダル数、カレン数、その他）
- GIMPS（探索対象：メルセンヌ数）
- en:Seventeen_or_Bust（終了）（探索対象：シェルピンスキー数に伴う素数）
- Riesel Sieve（終了）（探索対象：リーゼル数に伴う素数）
関連項目 編集
注釈 編集
数値 編集
出典 編集
- ^ a b “GIMPS Discovers Largest Known Prime Number: 282,589,933-1”. www.mersenne.org. 2018年12月25日閲覧。
- ^ “The largest known primes - Database Search Output”. Prime Pages. 2018年12月25日閲覧。
- ^ 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日閲覧。
- ^ Electronic Frontier Foundation, Big Prime Nets Big Prize.
- ^ “Best Inventions of 2008 - 29. The 46th Mersenne Prime”. Time (Time Inc). (2008年10月29日) 2012年1月17日閲覧。
- ^ “The Largest Known Prime by Year: A Brief History”. Prime Pages. 2016年1月20日閲覧。
- ^ 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].
- ^ Harris, Henry S (1999). The Reign of the Whirlwind. p. 252. hdl:10315/918.
- ^ Nicomachus' "Introduction to Arithmetic" translated by Martin Luther D'Ooge (p.52)
- ^ “Euclid's Elements, Book IX, Proposition 36”. 2016年12月5日閲覧。
- ^ ノリス・マクワーター, ed (1978). ギネスブック 世界記録事典 79年度版. 講談社. p. 116
- ^ ノリス・マクワーター, ed (1982). ギネスブック 82 世界記録事典. 大出健. 講談社. p. 121. ISBN 4-06-142667-2
- ^ アラン・ラッセル, ed (1986). ギネスブック'87 世界記録事典. 大出健. 講談社. p. 396. ISBN 4-06-202948-0
- ^ ピーター・マシューズ, ed (1992). ギネスブック'93. 講談社. p. 128. ISBN 4-88693-254-1