優れたインターネット検索メルセンヌプライム

グレート・インターネット・メルセンヌ素数探索（GIMPS ）は、ボランティアが無料で利用できるソフトウェアを使用してメルセンヌ素数を探索する共同プロジェクトです。

GIMPSは、 Prime95クライアントとそのLinuxポートであるMPrimeも作成したGeorge Woltmanによって1996年に設立されました。Scott Kurowskiは、1997年に彼が設立したEntropia社のボランティアコンピューティングソフトウェアを実証するために、バックエンドのPrimeNetサーバーを作成しました。GIMPSはMersenne Research, Inc.として登録されており、Kurowskiは執行副社長兼取締役を務めています。GIMPSは、研究目的でインターネット上で行われた最初の大規模なボランティアコンピューティングプロジェクトの1つと言われています。 ^{[ 2 ]}

2024年10月現在 このプロジェクトでは、18 個のメルセンヌ素数が発見されており、そのうち 16 個は発見当時、既知の最大の素数でした。既知の最大の素数は 2 ^136,279,841  −  1 (略して M _136,279,841 ) で、2024 年 10 月 12 日に Luke Durant によって発見されました。^{[ 3 ] [ 4 ]} 2025 年 6 月 18 日、このプロジェクトは 136,279,841 未満のすべての指数が少なくとも 1 回チェックされたことでマイルストーンを達成しました。^{[ 5 ]}

プロジェクトの開始から 2018 年まで、このプロジェクトは主にLucas–Lehmer 素数判定法(LL) ^{[ 6 ]}に依存していました。これは、メルセンヌ素数の判定に特化しており、特にバイナリコンピュータ アーキテクチャで効率的なアルゴリズムです。与えられたメルセンヌ数に適用する前に、試行除算フェーズがあり、小さな因数を持つ多くのメルセンヌ数を迅速に排除するために使用されます。Pollardのp − 1 アルゴリズムも、滑らかな因数を探すために使用されます。メイン実装 (Prime95) で使用されている LL のバリアントは、特に、 2 ^P − 1を法とする大きな数を効率的に二乗する方法を提供する、倍精度浮動小数点数を使用した無理数基底離散重み付き変換に基づいています。 ^{[ 7 ]}    

浮動小数点数の使用によって LL 計算にエラーが発生しないように、特別な注意が払われています。プログラムは、 128 回ごとに丸め誤差が 0.4 以下であることを検証するか、テスト対象の指数が使用中の FFT のサイズで処理できる最大指数サイズの 0.5% 以内である場合 (または特別なオプションを使用して要求された場合) は、すべての反復で丸め誤差が 0.4 以下であることを検証します。12 時間ごとに、プログラムは、^エラーを検出する確率が 50% であるヤコビ記号[ ^{8 ]}に基づく追加のエラー チェックを実行します。これらに加えて、完了した LL 計算はそれぞれ別のハードウェアで繰り返され、「二重チェック」されます。過去の二重チェック データに基づくと、重大なエラーが報告されなかった LL 計算のエラー率は 1.5% であり、少なくとも 1 つの重大なエラーが報告されたもののエラー率は 50% でした。^{[ 7 ]}

2018年、GIMPSは素数判定の代替オプションとして基底a = 3 ^{[ a ]}のフェルマー素数判定を採用し、 ^{[ 10 ]}フェルマー判定で素数である可能性が高いと検出されたメルセンヌ数の二重チェックとしてLL判定を維持しました。 ^{[ 11 ]}この新しい判定は、GIMPS用語ではPRP（probable prime）と呼ばれています。ロバート・ゲルビッチが考案した方法を使用することで、GIMPSはPRPの結果が正しく生成されることを「99.999+%」確信できます。^{[ 7 ]}その結果、LL判定は決定論的であり、フェルマー判定は確率論的であるにもかかわらず、^{[ b ]}フェルマー判定で素数ではないフェルマー擬似素数を見つける確率は、コンピュータのハードウェアエラーによるLL判定のエラー率よりもはるかに低くなります。^{[ 12 ]}  

2020 年 9 月に、^{[ 13 ] [ 14 ] [ 15 ]} GIMPS はKrzysztof Pietrzak によって提供された検証可能な遅延関数に基づく素数証明のサポートを開始しました。 ^{[ 16 ]}証明ファイルは、フェルマー素数判定の実行中に生成されます。これらの証明は、Gerbicz のエラーチェックアルゴリズムとともに、テス​​ト結果の正しさに対する完全な信頼性を提供し、二重チェックの必要性を排除します (証明のチェックは、元のフェルマー計算の 1/100 の時間で実行できます)。^{[ 7 ]}初めての LL テストは 2021 年 4 月に非推奨となり、LL はフェルマー判定によって見つかった可能性のある素数にのみ使用されるようになりました。^{[ 17 ]} PRP と LL の実行時間は似ています。^{[ 18 ]}優先される理由は、PRP の結果に対する信頼性が高いからです。^{[ 17 ]}

GIMPSには、既知の合成メルセンヌ数とフェルマー数を因数分解するサブプロジェクトもあります。これらは楕円曲線因数分解法とウィリアムズのp  +  1アルゴリズムを使用します。^{[ 19 ] [ c ]}

このプロジェクトは、i386コンピュータで動作するプログラムで1996 年 1 月に開始されました^{[ 20 ] [ 21 ] 。 [ 22 ] [ 23 ]}プロジェクトの名前は、初期の探索者の 1 人であり、29 番目のメルセンヌ素数の共同発見者である Luke Welsh によって考案されました。^{[ 24 ]}数か月以内に数十人が参加し、最初の年の終わりまでに 1,000 人以上が参加しました。^{[ 23 ] [ 25 ]}参加者の Joel Armengaud は、 1996 年 11 月 13 日にM _1,398,269の素数性を発見しました。 ^{[ 26 ]}それ以来、GIMPS は平均して 1 ～ 2 年ごとに新しいメルセンヌ素数を発見していますが、2024 年 10 月に発見された最新の最大の素数は、発見に 6 年近くかかりました。

2022年7月現在 GIMPSは、平均で約4.71ペタフロップス（またはPFLOPS）の持続的な総スループットを誇ります。^{[ 27 ]} 2012年11月には、GIMPSは95TFLOPSを維持し、^{[ 28 ]}理論上、GIMPS仮想コンピュータは世界で最も強力なコンピュータシステムTOP500の中で330位にランクインしました。^{[ 29 ]}当時、その前の順位はヒューレット・パッカードの「HP Cluster Platform 3000 BL460c G7」が保持していました。^{[ 30 ]} 2021年7月のTOP500の結果では、現在のGIMPSの数値はもはやリストに載りません。

これは、2010年初頭には約50TFLOPS、2008年中頃には30TFLOPS、2006年中頃には20TFLOPS、2004年初頭には14TFLOPSだった。

メルセンヌ素数はすべてM _p = 2 ^p − 1の形をしており、pは素数です。この表の中で最小のメルセンヌ素数は2 ^1398269 − 1 です。

最初の列は、すべてのメルセンヌ素数の（順序付けられた）シーケンスにおけるメルセンヌ素数のランクです。^{[ 36 ]} GIMPSは、35番目から始まるすべての既知のメルセンヌ素数を発見しました。

^{^ †} 2026年25日現在 81,307,409 は、それより小さいすべての素数指数が 2 回チェックされている最大の指数であるため、この表の 50 番目 (M _77232917 ) と 52 番目 (M _136279841 ) の間に未発見のメルセンヌ素数が存在するかどうかは検証されていません。したがって、この順位は暫定的なものです。さらに、141,081,007 は、それより小さいすべての素数指数が少なくとも 1 回テストされている最大の指数であるため、52 番目のメルセンヌ素数より小さいすべてのメルセンヌ数がテストされています。^{[ 38 ]}

^{^ ‡}数 M_136279841は 41,024,320 桁の十進数です。この数の大きさをイメージしやすくするために、これをディスクに保存すると、結果として得られるテキスト ファイルのサイズは約 42 メガバイトになります (プレーン テキスト形式のほとんどの書籍は 2 メガバイト未満です)。標準的なワード プロセッサのレイアウト (1 ページあたり 50 行、1 行あたり 75 桁) では、これを表示するのに 10,940 ページ必要になります。標準的なプリンター用紙を使用して片面印刷すると、約 22リーム(22 × 500 = 11,000 枚) の用紙が必要になります。

前述のとおり、ルーカス・レーマー法による結果はすべて、偽陽性と偽陰性の両方を避けるために二重チェックされます。陽性結果はより厳密に検査されます。この重要性は2003年に示されました。このとき、偽陽性がメルセンヌ素数としてサーバーに報告されましたが、検証に失敗しました。^{[ 39 ]}

素数の公式な「発見日」は、人間が最初にその素数の結果に気づいた日付であり、結果が最初にサーバーに報告された日付とは異なる場合があります。たとえば、M _74207281は 2015 年 9 月 17 日にサーバーに報告されましたが、その報告は 2016 年 1 月 7 日まで見過ごされていました。^{[ 40 ]}

• バークレー・オープン・インフラストラクチャ・フォー・ネットワーク・コンピューティング
• ボランティアによるコンピューティングプロジェクト一覧
• プライムグリッド

• 公式サイト