素数検出アルゴリズム入門：理論・実装・実務上の最適化
エバープレイ編集部はじめに — なぜ素数検出が重要か
素数検出（primality testing）は、数学的興味だけでなく暗号、乱数生成、数値計算など実務的用途でも中心的な役割を果たします。特に公開鍵暗号（RSA など）では大きな素数の生成と検証が必須です。本コラムでは基本的手法から最新の決定的手法、実装上の注意点、現場での最適化までを体系的に解説します。
基本的な考え方と単純なアルゴリズム
素数判定の最も直感的な方法は試し割り（trial division）です。n の平方根までの整数で割り切れるかどうかを調べます。実装は簡単ですが、時間計算量は O(√n) で、大きな n に対しては非現実的です。
- 単純試し割り：2 から ⌊√n⌋ まで試す。
- 奇数のみ試す：2 を別扱いして奇数だけ調べることで約半分の高速化。
- 素数列のみで試す：あらかじめ小さな素数を列挙してそれらでのみ割る（小さい素数で高速に除外できる）。
エラトステネスのふるいとその派生
範囲内のすべての素数を列挙する場合、エラトステネスのふるいが高速で簡便です。N までの素数を O(N log log N) 時間、O(N) メモリで求められます。大きな N を扱うとメモリが問題になるため、分割して処理するセグメント化ふるい（segmented sieve）を用います。
- セグメント化ふるい：メモリを節約して任意の範囲内の素数を列挙。
- ホイール法（wheel factorization）：2,3,5 などで周期的に飛ばすことで無駄な判定を減らす。
確率的素数判定法（高速で実用的）
大きな整数に対して一般的に用いられるのが確率的検定です。代表的なのはフェルマー検定、ミラー–ラビン検定、ソロヴェイ–シュトラス検定です。これらは高速で、誤判定確率を任意に小さくできます（ただしフェルマー検定はカルマー数などで誤判定しやすい）。
- ミラー–ラビン検定：基 a をいくつか選んで繰り返すランダム化検定。各ラウンドで合格する確率は通常 ≤1/4。十分なラウンド数で事実上決定的に近づく。
- ソロヴェイ–シュトラス検定：法論理を使った確率検定（実用面ではミラー–ラビンが一般的）。
- フェルマー検定：a^(n-1) ≡ 1 (mod n) をチェック。反例（カルマー数）が存在するため単独では不十分。
決定的素数判定法（証明可能な結果）
理論的には決定的な多項式時間のアルゴリズムも存在します。2002 年に提案された AKS（Agrawal–Kayal–Saxena）アルゴリズムは初めて多項式時間で決定的に素数判定を行いますが、実用面では定数因子が大きく高速化が課題です。
- AKS：Õ((log n)^c) の理論的保証。ただし実装は複雑で大きな n では非効率。
- ECPP（Elliptic Curve Primality Proving）：実務的に高速で、実際に大きな素数に対する証明に使われる。素数の証明書を生成できる。
ミラー–ラビンの決定性境界
興味深い点として、ミラー–ラビン検定は 64 ビット以下の整数に対して有限個の基 a を試すことで完全な決定的検定になります。例えば 64 ビット整数なら特定の基集合（2, 3, 5, 7, 11, 13, 17 等）だけで正確に判定可能であることが知られています（研究の更新があるので実装時には最新の結果を参照してください）。
複雑度と実行速度の実務的比較
代表的な手法の比較（概念的）：
- 試し割り：O(√n)、小さい n や素数リストの検証に有効。
- エラトステネス：N までの全列挙は O(N log log N)、範囲内列挙に最適。
- ミラー–ラビン：1 回のラウンドは O(k) のべき乗処理（k は桁数）、大きな n に高速。
- AKS：多項式時間だが定数が大きく現実的ではない。
- ECPP：大きな数に対して比較的高速かつ証明を生成可能。
実装上の注意点と最適化テクニック
実用的な実装では次のポイントが重要です。
- 小さな素数除去：ミラー–ラビンなどを行う前に小さな素因数（2,3,5,...数百まで）を先に除外すると高速化・安全性向上。
- 多倍長整数ライブラリの利用：GMP、OpenSSL の BIGNUM、Boost.Multiprecision など高性能ライブラリを用いる。
- 乗算アルゴリズムの選択：桁数が大きい場合は Karatsuba、Toom–Cook、FFT ベース乗算（Schönhage–Strassen）を使う。
- 定数時間実装：暗号用途では実行時間差によるサイドチャネル攻撃に注意し、時間や分岐を一定にする実装が必要。
- 並列化：セグメントふるいや確率検定の繰り返しは並列化しやすい。GPU を用いた高速な素数探索も研究・実装例がある。
大規模素数生成の実務フロー（例：RSA 鍵生成）
典型的なフローは次の通りです。
- ランダムな奇数を生成する（必要に応じて桁と形式を固定）。
- 小さな素数で素因数チェックを行い、早期除外。
- ミラー–ラビン検定を複数ラウンド実行して高い確率で素数を判定。
- 必要なら ECPP で証明書を生成（高セキュリティ要件の場合）。
よくある誤解と落とし穴
開発や採用時にしばしば見られる問題点：
- フェルマー検定だけで十分と誤信すること。カルマー数などの反例が存在するため、フェルマー単独は危険。
- 確率的検定でラウンド数が少なすぎる：暗号用途では誤判定を極めて低くする必要がある。
- 乱数の質が低い：大きな素数生成は良質な乱数に依存するため、暗号用途では安全な乱数源を必ず用いる。
実務上のベストプラクティス
現場での推奨事項は以下です。
- 大きな素数判定にはミラー–ラビンを複数ラウンド使用し、必要なら ECPP で証明を得る。
- 既存の検証済みライブラリ（OpenSSL、GMP、libsodium など）を利用する。手製実装はバグや脆弱性の原因になる。
- 暗号用途では定数時間実装と良質な乱数源を必須とする。
まとめ
素数検出はシンプルな試し割りから高度な確率的・決定的アルゴリズムまで幅があります。用途に応じて適切な手法を選ぶことが重要で、暗号や大規模探索ではミラー–ラビン＋小素数除去、必要なら ECPP の組み合わせが実用的です。パフォーマンス要件が高い場合は多倍長演算アルゴリズムや並列化、既存の高品質ライブラリの利用を検討してください。
参考文献
- Primality test — Wikipedia
- Miller–Rabin primality test — Wikipedia
- AKS primality test — Wikipedia
- Agrawal, Kayal & Saxena (2002) — "PRIMES is in P"
- Elliptic curve primality proving (ECPP) — Wikipedia
- GMP — GNU Multiple Precision Arithmetic Library
- OpenSSL BIGNUM primality functions
投稿者プロフィール
