20,000年前にさかのぼる不規則な印が刻まれた滑らかな骨の破片は、考古学者たちを困惑させていたが、彼らがある独特なことに気づくまでのことだった。その刻印は、タリーマークのような線であり、素数を表していた可能性がある。同様に、紀元前1800年の粘土板にはバビロニア数字が刻まれており、素数に基づく数体系が記述されている。
Ishango骨、Plimpton 322板、その他の歴史的遺物が示すように、素数は歴史を通じて人々を魅了し、とりこにしてきた。今日、素数とその性質は数論で研究されており、これは数学の一分野であり、現在も活発な研究領域である。
素数の歴史
非公式には、1より大きい正の自然数は、その数の点が1列または1行の長方形配列にのみ配置できる場合に素数である。例えば、11は素数である。なぜなら11個の点は1×11と11×1のサイズの長方形配列のみを形成するからである。逆に、12は素数ではない。なぜなら12個の点を使って3×4の点の配列を作ることができ、複数の行と複数の列を持つからである。数学の教科書では、素数を1より大きい整数で、その正の約数が1と自分自身のみである数として定義している。
数学史家のPeter S. Rudmanは、ギリシャの数学者が紀元前500年頃に素数の概念を最初に理解した可能性が高いと示唆している。
紀元前300年頃、ギリシャの数学者で論理学者のEuclidは、無限に多くの素数が存在することを証明した。Euclidは、有限個の素数が存在すると仮定することから始めた。そして、元のリストにない素数を考え出して矛盾を作り出した。数学の基本原理は矛盾のない論理的一貫性であるため、Euclidは元の仮定が偽でなければならないと結論づけた。したがって、無限に多くの素数が存在する。
この論証は無限に多くの素数の存在を確立したが、特に構成的ではなかった。Euclidは、すべての素数を昇順にリストアップする効率的な方法を持っていなかった。
中世において、アラブの数学者たちはギリシャの素数理論を発展させ、この時代にはhasam数と呼ばれていた。ペルシャの数学者Kamal al-Din al-Farisiは算術の基本定理を定式化し、これは1より大きい任意の正の整数が素数の積として一意に表現できることを述べている。
この観点から、素数は乗法を使って任意の正の整数を構築するための基本的な構成要素である。これは化学において原子が結合して分子を作るのと似ている。
素数は異なるタイプに分類できる。1202年、Leonardo Fibonacciは著書「Liber Abaci: Book of Calculation」で(2^p – 1)の形の素数を紹介した。ここでpも素数である。
今日、この形の素数はフランスの修道士Marin MersenneにちなんでMersenne素数と呼ばれている。既知の最大の素数の多くはこの形式に従っている。
初期の数学者の何人かは、pが素数であるときはいつでも(2^p – 1)の形の数が素数であると信じていた。しかし1536年、数学者Hudalricus Regiusは11は素数であるが(2^11 – 1)は素数ではないことに気づいた。これは2047に等しい。数2047は23×89として表現でき、この予想を反証した。
常に真ではないが、数論学者たちは(2^p – 1)のショートカットがしばしば素数を生み出し、大きな素数を探索する体系的な方法を提供することを理解した。
大きな素数の探索
数(2^p – 1)はpの値に比べてはるかに大きく、大きな素数を特定する機会を提供する。
数(2^p – 1)が十分に大きくなると、(2^p – 1)が素数かどうか、つまり(2^p – 1)個の点が1列または1行の長方形配列にのみ配置できるかどうかを確認することがはるかに困難になる。
幸い、Édouard Lucasは1878年に素数判定法を開発し、後にDerrick Henry Lehmerが1930年に証明した。彼らの研究により、潜在的なMersenne素数を評価する効率的なアルゴリズムが生まれた。紙上での手計算でこのアルゴリズムを使用して、Lucasは1876年に39桁の数(2^127 – 1)が170,141,183,460,469,231,731,687,303,715,884,105,727に等しく、その値が素数であることを示した。
M127としても知られるこの数は、手計算で検証された最大の素数のままである。この数は75年間、既知の最大素数の記録を保持した。
研究者たちは1950年代にコンピューターを使い始め、新しい大きな素数の発見のペースが加速した。1952年、Raphael M. Robinsonは5つの新しいMersenne素数を特定した。これはStandard Western Automatic Computerを使用してLucas-Lehmer素数判定法を実行したものである。
コンピューターが改良されるにつれて、特に1964年のCrayスーパーコンピューターの登場により、Mersenne素数のリストは増加した。無限に多くの素数が存在するが、研究者たちは(2^p – 1)の型に適合し、Mersenne素数である数がいくつあるかわからない。
1980年代初頭までに、研究者たちは無限に多くのMersenne素数が存在すると確信を持って信じるのに十分なデータを蓄積していた。彼らは平均してこれらの素数がどのくらいの頻度で現れるかを推測することさえできた。数学者たちはこれまでのところ証明を見つけていないが、新しいデータはこれらの推測を支持し続けている。
コンピューター科学者のGeorge Woltmanは1996年にGreat Internet Mersenne Prime Search（GIMPS）を設立した。この共同プログラムを通じて、誰でもGIMPSウェブサイトから自由に利用可能なソフトウェアをダウンロードして、個人のコンピューターでMersenne素数を探索できる。Webサイトには参加方法に関する具体的な指示が含まれている。GIMPSは現在18個のMersenne素数を特定しており、主にIntelチップを使用した個人用コンピューターで発見されている。このプログラムは平均して約1〜2年に1回新しい発見をしている。
既知の最大素数
退職したプログラマーのLuke Durantは、2024年10月に既知の最大素数の現在の記録である(2^136,279,841 – 1)を発見した。
M136279841と呼ばれるこの41,024,320桁の数は、特定された52番目のMersenne素数であり、公開されているクラウドベースのコンピューティングネットワークでGIMPSを実行することによって発見された。
このネットワークはNvidiaチップを使用し、17か国と24のデータセンターにわたって稼働した。これらの高度なチップは数千の計算を同時に処理することでより高速なコンピューティングを提供する。その結果、素数判定などのアルゴリズムの実行時間が短縮される。
Electronic Frontier Foundationは、大きな素数を特定することに対して賞金を提供する市民自由団体である。同団体は2000年と2009年に、最初の検証済み100万桁と1000万桁の素数に対して賞を授与した。
大きな素数愛好家の次の2つの挑戦は、最初の1億桁と10億桁の素数を特定することである。EFFの賞金として、それぞれ15万ドルと25万ドルが最初に成功した個人またはグループを待っている。
既知の最大の素数10個のうち8個がMersenne素数であるため、GIMPSとクラウドコンピューティングは記録破りの大きな素数の探索において重要な役割を果たす準備ができている。
大きな素数はサイバーセキュリティの多くの暗号化方法において重要な役割を果たしているため、すべてのインターネットユーザーが大きな素数の探索から恩恵を受けることになる。これらの探索はデジタル通信と機密情報の安全性を保つのに役立っている。
