2万年前の滑らかな骨片に不規則な模様が刻まれていたのを考古学者たちは不思議に思っていましたが、やがて奇妙な点に気づきました。それは、タリーマークのような線が素数を表わしていた可能性があるということです。同様に、紀元前1800年の粘土板にはバビロニア数字が刻まれており、素数に基づく記数法が記されています。
イシャンゴの骨、プリンプトン322粘土板、そして歴史上の他の遺物からもわかるように、素数は歴史を通じて人々を魅了し、魅了してきました。今日、素数とその性質は、数学の一分野であり、現在も活発に研究されている数論において研究されています。
素数の歴史
/Wikimedia Commons, CC BY-SA
非公式には、1より大きい正の数の点が、その個数の点を1列または1行の長方形配列にしか配置できない場合、その数は素数です。例えば、11個の点は1×11と11×1の長方形配列しか形成できないため、11は素数です。逆に、12個の点を使うと3×4の点の配列を複数行複数列に配置できるため、12は素数ではありません。数学の教科書では、素数は1とそれ自身以外の正の約数が存在しない1より大きい整数と定義されています。
数学史家のピーター・S・ラドマンは、紀元前500年頃にギリシャの数学者が最初に素数の概念を理解した可能性が高いと示唆している。
紀元前300年頃、ギリシャの数学者であり論理学者でもあったオイラーは、素数が無限に存在することを証明しました。オイラーはまず、素数の数は有限であると仮定しました。そして、元のリストにない素数を思いつき、矛盾を生じさせました。数学の基本原理は論理的に一貫しており、矛盾がないことであることから、オイラーは当初の仮定は誤りであると結論付けました。つまり、素数は無限に存在するということです。
この議論は無限個の素数の存在を証明したが、特に建設的ではなかった。オイラーはすべての素数を昇順で並べる効率的な方法を持っていなかった。
Eppstein/Wikimedia Commons
中世において、アラブの数学者たちは、当時ハサム数と呼ばれていたギリシャ人の素数理論を発展させました。ペルシャの数学者カマール・アッディーン・アル＝ファリシは、1より大きい任意の正の整数は素数の積として一意に表せるという算術の基本定理を定式化しました。
この観点から見ると、素数は、化学において原子が結合して分子を作るのと似た、乗算を使用して任意の正の整数を構成するための基本的な構成要素です。
素数は様々な種類に分類できます。1202年、レオナルド・フィボナッチは著書『算盤の書』の中で、(2 p – 1) という形式の素数（p も素数）を導入しました。
今日、この形式の素数は、フランスの修道士マラン・メルセンヌにちなんでメルセンヌ素数と呼ばれています。既知の最大の素数の多くは、この形式に従っています。
初期の数学者の中には、pが素数であれば(2 p - 1)の形で表される数は素数であると信じていた者もいました。しかし1536年、数学者フダルリクス・レギウスは、11は素数であるものの(2 11 - 1)は素数ではないことに気づきました。つまり、2047は11の89倍で表すことができ、この予想は反証されました。
常に正しいとは限りませんが、数論学者は、(2 p – 1) の近道によって素数が生成されることが多く、大きな素数を体系的に探す方法が得られることに気づきました。
大きな素数の探索
数 (2 p – 1) は p の値に比べてはるかに大きいため、大きな素数を識別する機会を提供します。
数 (2 p – 1) が十分に大きくなると、(2 p – 1) が素数であるかどうか、つまり、(2 p – 1) の点を 1 列または 1 行の長方形配列にのみ配置できるかどうかを確認することが非常に難しくなります。
幸運なことに、エドゥアール・ルーカスは1878年に素数検定法を開発し、後にデリック・ヘンリー・レーマーによって1930年に証明されました。彼らの研究は、メルセンヌ素数の可能性を評価する効率的なアルゴリズムを生み出しました。このアルゴリズムと紙の上での手計算を用いて、ルーカスは1876年に39桁の数（2の127乗- 1）が170,141,183,460,469,231,731,687,303,715,884,105,727に等しく、その値が素数であることを示しました。
M127としても知られるこの数は、手計算で検証された最大の素数であり、75年間、最大の素数として記録されてきました。
1950年代には研究者がコンピュータを使い始め、新たな大きな素数の発見ペースが加速しました。1952年、ラファエル・M・ロビンソンは、標準ウェスタン・オートマチック・コンピュータを用いてルーカス・レーマー素数検定を行い、5つの新たなメルセンヌ素数を特定しました。
コンピュータの改良に伴い、特に 1964 年に Cray スーパーコンピュータが登場して以来、メルセンヌ素数のリストは増え続けています。素数は無限に存在するものの、研究者たちは、その数のうちどれだけが (2 p – 1) のタイプに該当し、メルセンヌ素数であるかはわかっていません。
1980年代初頭までに、研究者たちはメルセンヌ素数が無限に存在すると確信できるだけのデータを蓄積していました。彼らは、これらの素数が平均してどれくらいの頻度で出現するかさえ推測することができました。数学者たちは今のところその証拠を見つけていませんが、新たなデータがこれらの推測を裏付け続けています。
コンピュータ科学者のジョージ・ウォルトマンは、1996年にGreat Internet Mersenne Prime Search（GIMPS）を設立しました。この共同プログラムでは、誰でもGIMPSのウェブサイトから無料でソフトウェアをダウンロードし、自分のパソコンでメルセンヌ素数を検索することができます。ウェブサイトには、参加方法に関する具体的な手順が記載されています。
GIMPSは現在までに18個のメルセンヌ素数を特定しており、主にIntelチップを搭載したパーソナルコンピュータ上で行われています。このプログラムは平均して1～2年ごとに新たな素数を発見しています。
最大の素数
引退したプログラマーのルーク・デュラント氏は、2024年10月に、現在知られている最大の素数（2 136,279,841 – 1）の記録を発見しました。M136279841と呼ばれるこの41,024,320桁の数は、特定された52番目のメルセンヌ素数であり、公開されているクラウドベースのコンピューティングネットワーク上でGIMPSを実行することで発見されました。
このネットワークはNVIDIAのチップを使用し、17か国24のデータセンターにまたがって稼働しています。これらの先進的なチップは、数千もの計算を同時に処理することで、より高速なコンピューティングを実現します。その結果、素数検定などのアルゴリズムの実行時間が短縮されます。
電子フロンティア財団は、大きな素数の発見に賞金を提供する市民自由団体です。2000年と2009年には、初めて検証された100万桁と1000万桁の素数に賞金を授与しました。
巨大素数愛好家たちの次の2つの挑戦は、最初の1億桁と10億桁の素数を特定することです。最初の成功者またはグループには、それぞれ15万ドルと25万ドルのEFF賞金が授与されます。
知られている最大の素数 10 個のうち 8 個はメルセンヌ素数であるため、GIMPS とクラウド コンピューティングは、記録を破る大きな素数の探索において重要な役割を果たすことになりそうです。
大きな素数はサイバーセキュリティにおける多くの暗号化手法において重要な役割を果たしているため、すべてのインターネットユーザーは大きな素数の探索から恩恵を受けることができます。これらの探索は、デジタル通信と機密情報の安全を守るのに役立ちます。
ジェレミア・バーツ、ノースダコタ大学数学准教授。この記事はクリエイティブ・コモンズのライセンスに基づきThe Conversationから転載されました。原文はこちら。
