素数判定アルゴリズム入門：理論・実装・実務での使い分けガイド

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

概要：素数判定の重要性と分類

素数判定（primality testing）は、数学理論だけでなく暗号技術や数値計算の基礎として極めて重要です。RSAのような公開鍵暗号は大きな素数の生成に依存しており、実務では高速かつ信頼できる判定法が必要です。素数判定アルゴリズムは大きく「決定性アルゴリズム（確実に正否を判定）」と「確率的アルゴリズム（誤判定確率が極めて小さい）」に分かれます。ここでは基本手法から最新の理論、実装上の最適化、実務での選び方まで詳述します。

基本的な手法

最も直感的な方法は試し割り（trial division）です。2から√nまでの整数で割り切れるか試すもので、nが小さい場合や素数候補を前処理する際のスクリーニングとして有効です。ただし計算量はO(√n)であり、大きな数には使えません。

素数列を効率的に列挙するならばエラトステネスのふるい（sieve of Eratosthenes）やその改良版（セグメント化、ホイール最適化）を使います。これらは連続した範囲の候補を一括でふるい落とすのに適しており、素数候補のプレフィルタとして有効です。

確率的テスト：Miller–Rabin とその派生

Miller–Rabin（ミラー–ラビン）検定は実用上最も広く用いられる確率的素数判定法です。与えられた奇数nについて、n-1 を 2^s * d の形に分解し、基底aについて a^d (mod n) やそれに続く二乗系列をチェックします。特定の条件を満たさなければ合成数と判定できますが、一定の確率で「強擬素数（strong probable prime）」となり誤判定が生じます。誤判定確率は基底を複数選ぶことで指数関数的に低下します。

実務ではランダムな基底で数十回試行することが一般的で、例えば40ラウンドで誤判定確率はほぼ無視できるレベル（2^-80 より小さい）になります。特筆すべきは、Miller–Rabin は特定の固定基底集合を使えば決定的になる範囲が知られている点です。例えば64ビット整数以下については基底 {2,325,9375,28178,450775,9780504,1795265022} のテストで決定的に素数判定できます。

Baillie–PSW（BPSW）検定は、Miller–Rabin（基底2）とLucas擬素数検定を組み合わせたもので、非常に高速かつ実用上ほぼ確実とされています。これまでに知られている反例は非常に大きな範囲で存在せず、多くのライブラリでデフォルトの判定法として採用されています。

決定的アルゴリズム：AKS と ECPP など

2002年に発表されたAKS（Agrawal–Kayal–Saxena）アルゴリズムは、素数判定が多項式時間で解けることを初めて理論的に示しました。AKS は理論的に重要ですが、実装効率は必ずしも高くなく、最初の提案では計算量が O((log n)^12) 程度とされ、その後の改良で O((log n)^6) 程度に落とせるという研究があります。実務で広く使われるまでには至っていませんが、理論的には重要なブレイクスルーです。

実務的に利用される決定的手法としては ECPP（Elliptic Curve Primality Proving）が挙げられます。ECPP は楕円曲線の理論を利用して素性証明（certificate）を生成し、生成された証明は短時間で検証できます。Primo（市販/学術用ソフト）や一部のライブラリで実装されており、巨大な素数に対する実際的な証明手段として信頼されています。

その他、APR-CL（Adleman–Pomerance–Rumely / Cohen–Lenstra などの改良）といった準決定的・決定的手法もありますが、実務での利用頻度はECPPに次ぎます。

計算量と現実的な速度

各アルゴリズムの理論的計算量はビット演算モデルで議論されます。簡単にまとめると：

  • 試し割り：O(√n) の算術演算（ビット複雑度は非常に高い）
  • Miller–Rabin：k回のモジュラー指数演算で、実装次第だが実用上高速（ビッグオーで約 O(k * log^3 n) と表現されることが多い）
  • AKS：多項式時間（最初は高次だが理論上は決定性）
  • ECPP：実用上非常に高速で、巨大な数でも扱える（平均的には多項式近似の振る舞い）

実装では乗算のアルゴリズム（学校算術、Karatsuba、FFT乗算など）や多倍長整数ライブラリ（GMPなど）に依存して速度が大きく変わります。

実装上の最適化と実務での採用法

実務的な素数生成や判定の一般的なワークフロー：

  • 小さい素数リストでのプレフィルタ（素因数候補を除外）
  • ホイールやセグメント化したふるいで候補を効率的に生成
  • まず1〜数ラウンドのMiller–Rabinで高速に合成数を除去
  • 必要に応じてBaillie–PSWや追加のMRラウンドで確度を上げる
  • 厳密な証明が必要な場合はECPPで素性証明を作成

ライブラリ面では、GMP（GNU Multiple Precision Arithmetic Library）が多倍長整数演算の事実上の標準であり、OpenSSL や libgcrypt 等も素数生成機能を提供しています。OpenSSL の BN_generate_prime_ex は複数のMRラウンドとオプションでの証明生成をサポートします。

実務での注意点

暗号用途では、単に“十分に大きい数”を素数とするだけでなく、乱数生成器の品質、生成プロセスの予測不可能性、そして偶発的な弱点（例：共通因子を持つ素数の生成）に注意する必要があります。素数候補を生成する際はソルトやエントロピー源を慎重に扱い、生成後にGCDによる共通因子チェックを行うのが一般的です。

まとめ：用途に応じた選択基準

小〜中規模の用途や暗号用鍵生成では、プレフィルタ＋Miller–Rabin（数十ラウンド）あるいはBaillie–PSWの組合せが高速かつ実用的です。厳密な数学的証明が必要な場面や学術研究ではECPPやAPR系、理論的興味ならAKSを検討します。実装では高精度の多倍長整数ライブラリを使い、プレフィルタ（小さい素数による除外）やセグメントふるいで計算量を減らすのが鍵です。

参考文献

Miller–Rabin primality test — Wikipedia
Agrawal, Kayal, Saxena: PRIMES is in P (AKS original paper, 2002)
Baillie–PSW primality test — Wikipedia
Elliptic Curve Primality Proving — Wikipedia
GMP: GNU Multiple Precision Arithmetic Library
OpenSSL BN_generate_prime_ex ドキュメント
AKS primality test — Wikipedia

カテゴリー
IT
前の記事
感動映画の秘密：心を揺さぶる物語・技法・厳選おすすめガイド
2025年12月11日
次の記事
ギャング映画の系譜と魅力：歴史・様式・代表作から現代的変容まで
2025年12月11日