素数判定 — 数が素数であるかを判定する方法

手法と特性

素数判定は、決定的か確率的か、また計算量によって分類できる。決定的判定は、数が素数であることの証明を与えるか、または因数を特定する。確率的判定は、「おそらく素数」であると報告する際にごく小さい誤りの可能性を伴うものの、合成数を高速に識別する。効率、メモリ使用量、検証可能な証明書を作成しやすいかどうかは、代表的な設計上のトレードオフである。

代表的なアルゴリズム

• 試し割り：平方根までの整数で割り切れるかを試す。単純だが、大きな入力には実用的でない。
• フェルマーテストと関連する検定：nを法とする冪の性質を用いる。高速だが、カーマイケル数の影響を受けやすい。
• ミラー–ラビン判定法：複数の基数を用いると非常に信頼性が高い、広く使われる確率的判定法である。数論上の一定の仮定の下では、変種は決定的となる。
• AKS：2002年に発見された決定的な多項式時間判定法であり、素数判定がPに属することを示した。
• 楕円曲線法とECPP：しばしば証明書を生成でき、非常に大きな数に対しても良好に機能する実用的なアルゴリズムである。

歴史と発展

素数判定は歴史的に、初等的な整除性の確認から、洗練された代数的・確率的手法へと発展してきた。大規模な暗号の実用化を可能にした乱択判定法や、決定可能性と計算量に関する理論的問題を解決した決定的多項式時間アルゴリズムは、重要な進展である。実用的な実装では、高速な確率的スクリーニングと、最後の決定的判定または証明書作成の段階を組み合わせることが多い。

応用と証明書

素数判定は暗号以外にも、計算数学や、素数を法とすることを必要とする数学的対象の構成で用いられる。形式的な証明が必要な場合、多くの判定法は素数証明書を生成する。これは、第三者が判定全体を再実行するより少ない計算で、その数の素数性を検証できるコンパクトなデータである。例として、Pratt証明書、ECPPによって生成される証明書、ポックリントンの定理の変種に基づく証明書がある。

重要な区別

判定法を選ぶ際には、入力の大きさと絶対的な確実性の必要性を考慮する。ミラー–ラビン判定法のような確率的判定法は、通常の用途では高速で誤りが無視できるほど小さい。法的・科学的・プロトコル上の証明が求められる場合には、決定的手法または証明書が望ましい。実装では、速度、信頼性、証明書の生成または検証に要する労力の均衡が図られる。