メルセンヌ数とは何か？定義・性質・ルーカス–レーマー検定とGIMPSによる大規模探索

2025年11月25日 最終更新日時 : 2025年11月25日 エバープレイ編集部

メルセンヌ数とは — 定義と基本性質

メルセンヌ数（Mersenne number）は 2^p − 1 の形をした自然数を指します。ここで p は正の整数であり、標準的な表記では M_p = 2^p − 1 と書きます。p が合成数（例えば p = ab, a,b > 1）のとき、M_p は必ず合成数になります（因数分解の恒等式 2^{ab} − 1 = (2^a − 1) × (2^{a(b−1)} + … + 1 を使うため）。したがって、メルセンヌ素数（Mersenne prime）となり得るためには p が素数であることが必要条件です（ただし十分条件ではありません）。

歴史的背景

メルセンヌ数の名は 17 世紀のフランソワ・ド・メルセンヌ（Marin Mersenne）に由来します。メルセンヌはいくつかの指数 p に対して 2^p − 1 が素数であるかどうかを手計算で調べ、古典的に知られる小さなメルセンヌ素数（p = 2, 3, 5, 7, 13, 17, 19, 31 など）を列挙しました。その後 19〜20 世紀にかけてルーカスやレーマーらによって判定法が整備され、コンピュータ時代には大規模な分散計算プロジェクト（GIMPS）によって非常に大きなメルセンヌ素数が次々と発見されました。

代表的な性質と定理

  • 必要条件：M_p が素数であるためには p は素数である（しかし p が素数でも M_p が素数とは限らない）。

  • 素因数の形：任意の素因数 q が M_p を割るとき、q の位数に関する議論から p は q−1 を割る（つまり q ≡ 1 (mod p)）。このため q は kp + 1 の形をとる。

  • ユークリッド＝オイラーの定理（完全数との関係）：2^p − 1 が素数（メルセンヌ素数）であるとき、2^{p−1}(2^p−1) は完全数（自分自身を除く約数の和がその数自身になる数）になります。逆に、偶数の完全数は必ずこの形に表されます（偶数の完全数はすべてメルセンヌ素数に対応する）。奇数の完全数の存在は未解決問題です。

メルセンヌ素数の判定法 — ルーカス＝レーマー検定

メルセンヌ数 M_p の素性判定にはルーカス＝レーマー（Lucas–Lehmer, LL）検定が広く使われます。p が奇素数のとき、次の漸化列を定義します：

  • s_0 = 4

  • s_{n+1} = s_n^2 − 2 (ただし計算は M_p を法として行う)

このとき、M_p は素数であることと同値である条件は s_{p−2} ≡ 0 (mod M_p) です。LL 検定はメルセンヌ数専用に非常に効率的に設計された決定的アルゴリズムであり、GIMPS 等のプロジェクトで用いられています（p = 2 の場合は M_2 = 3 が素数で例外的に扱う）。

計算技術 — 大きな Mersenne を扱うための工夫

指数 p が大きくなると M_p の桁数は p に比例して増えます（桁数はおおよそ p × log10 2）。大きな M_p を LL 検定で扱う際には、高速な大整数乗算と剰余演算が鍵になります。具体的には：

  • FFT に基づく乗算（Schönhage–Strassen, Fürer 以降の最適化）を用いて非常に長いビット列の乗算を高速化する。

  • Mersenne 特有の補助法（Mersenne reduction）：2^p−1 を法にとる剰余はビットシフトと加算で効率よく計算でき、実装上の高速化が可能。

  • 事前の素因数探索や確率的なPRP（probable prime）テストにより、完全な LL 検定を行う前の「ふるい」を掛ける。

GIMPS と分散検索

Great Internet Mersenne Prime Search（GIMPS）はボランティアの分散コンピューティングでメルセンヌ素数を探索するプロジェクトです。参加者のマシンに専用ソフト（Prime95 等）を入れて計算を行い、新しい候補が見つかると検証（通常は複数ノードでの再確認と LL 検定）されます。非常に大きなメルセンヌ素数はすべてこの方式で発見されてきました。

2018 年 12 月に発見された 2^82,589,933 − 1（約 2,486 万桁）は、私の知識が最新に保たれている 2024 年 6 月時点でも最大既知の素数としてしばしば参照されます（新記録が出る可能性は常にあります）。

応用と限界

メルセンヌ数やメルセンヌ素数は理論・実践の双方で興味深い特徴を持ちます：

  • 数学的関心：素数論、完全数論、数論的性質の研究材料として重要です。

  • 乱数生成：Mersenne の名を冠した疑似乱数生成器「Mersenne Twister（MT19937）」は周期が 2^19937 − 1（非常に長い）の擬似乱数生成器として広く使われます。名称はメルセンヌ数にちなんでいますが、暗号用途の安全性を重視した設計ではありません。

  • 計算上の工夫：2^k − 1 の形を利用した高速なモジュロ演算は暗号等の場面で役立つことがあります。ただし暗号で通常選ばれる素数は構造的弱点を避ける観点から慎重に選ばれるため、メルセンヌ素数が直接使われる例は限定的です。

よくある誤解と注意点

  • 「p が素数ならば M_p は素数」ではない：例えば p = 11 のとき M_11 = 2047 = 23 × 89 となり合成です。

  • メルセンヌ数の検索は「指数が素数であれば候補」というだけで、実際の素性確認は LL 検定等で決定的に行う必要がある。

  • 現行の最大既知素数はメルセンヌ素数が占めることが多いが、これはメルセンヌ数に対する特別な効率的検定法の存在と分散計算による探索戦略が要因であり、他の形の数に対して素数が存在しないわけではない。

まとめ

メルセンヌ数は単純な形（2^p − 1）に見えて、素数論や計算機科学において深い意味と多くの応用・課題を持つ対象です。ルーカス＝レーマー検定という強力な道具と FFT ベースの高速算術、分散計算の組み合わせによって、現代では数百万〜数千万桁級のメルセンヌ素数が確認されています。研究と探索は現在も活発であり、未発見の大きなメルセンヌ素数が将来発見される可能性は十分にあります。

参考文献

カテゴリー
IT
前の記事
フェルマー数とは何か：素数性・ペパンの判定・作図との関係と現状の課題New!!
2025年11月25日
次の記事
確率的アルゴリズムの実務ガイド：モンテカルロ・ラスベガス・ZPPの分類と応用、乱数品質と実装のポイントNew!!
2025年11月25日