素数判定の総合ガイド：ミラー–ラビン法からAKSまでの手法と実装・暗号利用の要点

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

素数判定（Primality Testing）とは何か — 概要

素数判定は、与えられた整数 n が素数か合成数（合成数 = 素因数を持つ数）かを判定する問題です。単純に見えても計算量や確率的誤判定の扱い、暗号用途での実用性を考えると非常に奥が深い分野です。ここでは基本的な手法から理論的結果、実装上の注意点や暗号での利用までを詳しく解説します。

基本的な手法

以下に代表的な素数判定法を挙げ、長所と短所を示します。

  • 試し割り（Trial division）

    2 から sqrt(n) までの整数で割り切れるか調べる最も直接的な方法。確実に判定できるが計算量は O(√n) で大きな数には現実的ではありません。小さい n の場合や高速化（偶数除去、素数候補のみを試すなど）を施した場合に有用です。

  • エラトステネスの篩（Sieve）

    範囲内の多くの素数を一括で求めるのに適しており、個々の値に対する判定ではなく「範囲探索」に向きます。大きな一つの数（例えば 1024 ビット）の判定には不向きです。

  • フェルマーの小定理に基づく検定（Fermat primality test）

    a^(n-1) ≡ 1 (mod n) を満たすかを確認することで合成数を弾きます。高速だがフェルマー擬素数（Fermat pseudoprime）やカルマイケル数に対して誤判定することがあるため、単独では不十分です。

  • ミラー–ラビン確率的素数判定（Miller–Rabin）

    現在の実用上の標準はミラー–ラビン（MR）法です。n-1 を 2^s·d と分解し、与えた基 a に対して a^d mod n から特定の条件を満たすかを調べます。非素数 n に対して「誤って素数と判定される」確率は高々 1/4（ある定理による下界）で、異なる独立なランダム基を k 回試すと誤判定確率は ≤ 4^(-k) に急速に減少します。計算は高速で大きな数にも適しています。

  • BPSW（Baillie–PSW）テスト

    1 回の強いミラー–ラビン（base 2）と 1 回の Lucas 署名型検定を組み合わせた経験的に非常に信頼できる判定法。現在まで実用範囲で誤判定例が知られていないため、一部の実装で採用されていますが、理論的に誤判定が無いことは保証されていません。

  • AKS（決定性多項式時間アルゴリズム）

    Agrawal–Kayal–Saxena により 2002 年に示された「PRIMES is in P」の結果。素数判定を多項式時間で行えることを示したブレイクスルーですが、実装上は定数や次元が大きく、実用的には今も確率的手法に劣る場合が多いです。理論的意義は非常に大きいです。

  • 楕円曲線素数証明（ECPP）などの確定的証明法

    楕円曲線を用いて与えられた数が本当に素数であることを証明する手法。実際の大きな数（数千ビット）に対しても比較的効率的に "証明（certificate）" を生成でき、生成された証明を検証することで決定的に素数と断言できます。暗号鍵の検証などで利用されます。

ミラー–ラビン法の仕組み（もう少し詳しく）

ミラー–ラビンは「強い確率的素数判定法（strong probable prime test）」と呼ばれます。手順はおおむね次の通りです。

  • n-1 を 2^s × d とし、d は奇数にする（n 偶数や小さい因子は事前に排除）。

  • 基 a（1 < a < n-1）を選び、x = a^d mod n を計算する。

  • もし x = 1 または x = n-1 なら、その a に対して n は「合成数の確率が低い（合格）」とする。

  • 上の条件を満たさなければ、x を自乗して n-1 までの s-1 回ループし、途中で x が n-1 になれば合格、最後までなら不合格（つまり確実に合成数）とする。

重要な性質として、合成数 n に対してミラー–ラビンの「偽証人（witness）」を与えない a の割合は 1/4 以下であることが示されており（ある定理に基づく）、したがってランダムに k 個の a を試すと誤判定確率は最大で 4^(-k) になります。

確定性を得るには（実用上の工夫）

  • 固定基による決定性：有限の上限までの n に対しては、いくつかの固定された基の集合だけでミラー–ラビンが決定的になるという結果が知られています（例えば 32bit や 64bit 範囲についての既知の基集合）。これにより 64 ビット以下の整数を確定的に判定可能な高速実装があります。

  • BPSW の組合せ：経験的に高信頼の結果が得られるため、大規模ソフトウェアやライブラリで採用されることが多いです。

  • 証明付き判定（ECPP 等）：暗号交換で「絶対に素数である」として扱いたい場合は、ECPP 等で素数証明を生成し、これを保存・検証します。生成に時間はかかりますが検証は比較的速いです。

数学的および実用的な注意点

  • フェルマー擬素数とカルマイケル数：フェルマー検定のみを使うと誤判定する例（例えばカルマイケル数）が存在します。ミラー–ラビンはこの問題を大幅に緩和しますが、完全に排除するには複合的手法や証明が必要です。

  • 乱数の質と鍵生成：暗号用途では「ランダムに選んだ候補が素数である確率」を考え、候補生成に使う乱数の品質が重要です。偏った乱数源だと安全性が損なわれます。

  • 実装の罠：モジュラ累乗（a^d mod n）の実装ミス、境界条件（小さい因子の除去）、多倍長整数ライブラリのバグなどにより誤った判定をする可能性があります。既存の信頼されるライブラリや十分なテストを用いることが推奨されます。

計算量と実用例

試し割りは O(√n)（ビット長 L = log n と書くと指数時間級）、一方でミラー–ラビンは一般に多倍長整数のべき乗計算を繰り返すアルゴリズムであり、実装と使用するアルゴリズム次第で非常に高速です。暗号用途（RSAなど）では 1024〜4096 ビット程度の素数を生成する必要があり、通常はミラー–ラビンなどの確率的手法で十分高速かつ信頼できる判定を行い、場合によっては証明法で裏付けします。

実装例とライブラリ

  • 多くの暗号ライブラリ（OpenSSL 等）や多倍長整数ライブラリ（GMP 等）は、ミラー–ラビンを中心とした確率的判定を実装しています。実装の詳細はライブラリのバージョンや設定によって異なるため、利用時はドキュメントを確認してください。

  • 高信頼を要する場面（公開鍵の検証、数学的証明の発行等）では ECPP による証明生成を行う実装も使われます。

まとめ

素数判定には「単純で確実だが遅い」方法から「高速で確率的なもの」、「数学的に決定的だが実用上は重いもの」まで多様な手法があります。実務ではミラー–ラビンなどの確率的手法が主流ですが、用途によっては BPSW のような経験的に安全な組合せや、ECPP による証明を用いることがあります。最近の理論的進展（AKS）により「多項式時間での確定性」は達成されていますが、実運用では速度と確実性のバランスをどう取るかが重要です。

参考文献

カテゴリー
IT
前の記事
リュカ–レーマー・テスト完全ガイド：メルセンヌ素数の素数判定と高速実装のコツNew!!
2025年11月25日
次の記事
3Dモデル制作の完全ガイド：ワークフロー・PBR・フォーマット・最適化・ライセンスまで徹底解説New!!
2025年11月25日