素数判定

素数判定法は、入力された数が素数であるかどうかを判定するアルゴリズムです。数学の分野の中でも、暗号学などに用いられています。整数因数分解とは異なり、素数判定法は一般的に素因数を与えるのではなく、入力された数が素数であるかどうかだけを示します。因数分解は計算上難しい問題と考えられていますが、素数判定法は比較的容易です（実行時間は入力数のサイズに対して多項式時間です）。素数判定法の中には、数が素数であることを証明するものもあれば、ミラー・ラビン判定法のように、数が合成数であることを証明するものもあります。そのため、後者は素数判定法というよりも、合成数判定法と呼ぶ方がより正確かもしれません。

最も単純な素数判定は試行除算です。入力された数値が与えられた場合、${\displaystyle n}$2 から 1 までの素数で割り切れるかどうかを確認します。${\displaystyle {\sqrt {n}}}$（つまり、分割しても余りが出ないかどうか）。もしそうなら、${\displaystyle n}$合成数である。そうでなければ、素数である。^{[ 1 ]}すべての約数${\displaystyle p\geq {\sqrt {n}}}$約数を持つ必要があります$\displaystyle {\frac {n}{p}}\leq {\sqrt {n}}}$、そして素因数${\displaystyle q}$の${\displaystyle {\frac {n}{p}}}$したがって、素因数を探すと、${\displaystyle {\sqrt {n}}}$それで十分です。

例えば、100という数を考えてみましょう。100の約数は次のとおりである。

1、2、4、5、10、20、25、50、100。

可能な約数がすべて${\displaystyle n}$テストを行うと、一部の約数は2回見つかるでしょう。これを観察するために、100の約数のペアのリストを考えてみましょう。

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$。

過去の製品${\displaystyle 10\times 10}$これらは、先に登場した製品の逆です。たとえば、${\displaystyle 5\times 20}$そして${\displaystyle 20\times 5}$互いに逆の関係にある。さらに、2 つの約数のうち、$5 ≤ √100 = 10$そして${\displaystyle 20\geq {\sqrt {100}}=10}$この観察は、すべてに一般化される。${\displaystyle n}$: すべての約数ペア${\displaystyle n}$以下の約数を含む${\displaystyle {\sqrt {n}}}$アルゴリズムは、以下の約数を探すだけでよい。${\displaystyle {\sqrt {n}}}$すべての約数ペアの検出を保証するため。^{[ 1 ]}

また、2は100を割り切る素数であり、これは100が素数ではないことを即座に証明します。算術の基本定理により、1を除くすべての正の整数は少なくとも1つの素数で割り切れます。したがって、アルゴリズムは、以下の素因数のみを探索する必要があります。${\displaystyle {\sqrt {n}}}$。

別の例として、このアルゴリズムが17の素数性をどのように判定するかを考えてみましょう。$4<√17}<5$、そして唯一の素数$\displaystyle \leq \sqrt {17}}$2と3です。どちらも17を割り切らないので、17は素数であることが証明されます。最後の例として、221を考えてみましょう。${\displaystyle 14<{\sqrt {221}}<15}$、そして素数$\displaystyle \leq \sqrt {221}}$2、3、5、7、11、13です。それぞれを確認すると、${\displaystyle {\frac {221}{13}}=17}$221が素数ではないことを証明する。

素数のリストを計算する場合${\displaystyle \leq {\sqrt {n}}}$実現不可能、すべての数値は${\displaystyle 2}$そして${\displaystyle {\sqrt {n}}}$約数を簡単に（そしてゆっくりと）チェックできます。簡単な改善策は、2 と 3 から 1 までの奇数のみで割り切れるかどうかをテストすることです。${\displaystyle {\sqrt {n}}}$偶数で割り切れるということは、2で割り切れることを意味するからです。

この方法はさらに改善できる。5より大きい素数はすべて次の形式であることに注目してください。${\displaystyle 6k+i}$非負整数の場合${\displaystyle k}$そして${\displaystyle i\in \{1,5\}}$実際、すべての整数は次の形式です。${\displaystyle 6k+i}$正の整数${\displaystyle k}$そして${\displaystyle i\in \{0,1,2,3,4,5\}}$2 は割り切れるので${\displaystyle 6k,6k+2}$、 そして${\displaystyle 6k+4}$、そして3分割${\displaystyle 6k}$そして${\displaystyle 6k+3}$3より大きい素数の場合、mod 6で可能な余りは1と5のみです。したがって、より効率的な素数判定法は、${\displaystyle n}$テストするのは${\displaystyle n}$が 2 または 3 で割り切れる場合は、その形式のすべての数をチェックします。${\displaystyle 6k+1}$そして${\displaystyle 6k+5}$それは${\displaystyle \leq {\sqrt {n}}}$これは、すべての数値をテストするよりもほぼ3倍速い。${\displaystyle {\sqrt {n}}}$。

さらに一般化すると、${\displaystyle p_{m}}$（${\displaystyle m}$（ 番目の素数）は、${\displaystyle p_{m}\#\cdot k+i}$、 どこ${\displaystyle \{k,i\in \mathbb {Z} \mid 0\leq i<p_{m}\#\land {\text{gcd}}\left(p_{m}\#,i\right)=1\}}$そして${\displaystyle p_{m}\#}$原始的なもの、つまり最初のものの産物${\displaystyle m}$素数。

例えば、${\displaystyle p_{3}\#=2\cdot 3\cdot 5=30}$すべての整数は次の形式です。${\displaystyle 30k+i}$、 どこ${\displaystyle \{k,i\in \mathbb {Z} \mid 0\leq i<30\}}$. 2 は割り切れる${\displaystyle 0,2,4,\dots ,28}$3 分割${\displaystyle 0,3,6,\dots ,27}$、そして5は分割します${\displaystyle 0,5,10,\dots ,25}$したがって、30より大きいすべての素数は次の形式になります。${\displaystyle 30k+i}$のために${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$もちろん、この形式のすべての数字が${\displaystyle p_{m}\#\cdot k+i}$と${\displaystyle i}$互いに素な${\displaystyle p_{m}\#}$素数である。例えば、${\displaystyle 19\cdot 23=437=210\cdot 2+17=p_{4}\#\cdot 2+17}$は素数ではないが、17は互いに素である。${\displaystyle p_{4}\#=2\cdot 3\cdot 5\cdot 7}$。

その間${\displaystyle \lim _{m\to \infty }{\frac {\phi \left(p_{m}\#\right)}{p_{m}\#}}=0}$、 どこ${\displaystyle \phi \left(m\right)}$オイラーのトーシェント関数は、以下のすべての素数による割り切れるかどうかをチェックします。${\displaystyle p_{m}\#}$は依然として必要です。前述の観察と同様の観察を再帰的に適用することで、エラトステネスの篩が得られます。

これらの方法（および以下で述べる他のすべての方法）を高速化する1つの方法は、200までのすべての素数など、特定の上限までのすべての素数のリストを事前に計算して保存することです。（このようなリストは、エラトステネスの篩、または各増分をテストするアルゴリズムによって計算できます。）${\displaystyle m}$既知のすべての素数に対して${\displaystyle \leq {\sqrt {m}}}$) そして、テストする前に${\displaystyle n}$大規模な方法による素数判定、${\displaystyle n}$まず、リストにある素数で割り切れるかどうかを確認します。もしそれらの数のいずれかで割り切れる場合は合成数であり、それ以上の判定は省略できます。

単純だが非効率的な素数判定法は、ウィルソンの定理を使用する。ウィルソンの定理は次のように述べている。${\displaystyle p}$素数であるのは、以下の条件を満たす場合に限る。

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

この方法は約${\displaystyle p}$モジュラー乗法は実用的ではないが、素数とモジュラー剰余に関する定理は、より実用的な多くの方法の基礎となっている。^{[ 2 ]}

これらは実際にはうまく機能するように見えるテストですが、証明されていないため、厳密に言えばアルゴリズムではありません。フェルマー素数判定法とフィボナッチ数列判定法はその簡単な例であり、組み合わせると効果的です。ジョン・セル​​フレッジは、 pが奇数で、p ≡ ±2 (mod 5) である場合、以下の2つが両方とも成り立つ場合にpは素数であると推測しました。

• 2 ^{p −1} ≡ 1 (mod p )
• f _{p +1} ≡ 0 (mod p )、

ここで、f _kはk番目のフィボナッチ数です。最初の条件は、基数 2 を使用したフェルマー素数判定です。

一般に、p ≡ a (mod x ² +4) （ただし、a は(mod x ² +4)の非剰余数）である場合、以下の条件が満たされればpは素数であるはずです。

• 2 ^{p −1} ≡ 1 (mod p )
• f ( x ) _{p +1} ≡ 0 (mod p )

f ( x ) _kはxにおけるk番目のフィボナッチ多項式です。

セルフレッジ、ポメランス、ワグスタッフは、反例または反例が存在しないという証明に対して合計620ドルを提供した^{[ 3 ]} 。現在、その賞金は数論財団から支払われる予定である。

確率的テストは、合成数に騙される確率の証明可能な上限を提供する点で、ヒューリスティックよりも厳密です。よく使われる素数判定法の多くは確率的テストです。これらのテストでは、テスト対象の数nの他に、サンプル空間からランダムに選択された数aを使用します。通常のランダム化素数判定法では、素数が合成数として報告されることはありませんが、合成数が素数として報告される可能性はあります。エラーの確率は、独立して選択された複数のaの値でテストを繰り返すことで低減できます。よく使われる 2 つのテストでは、任意の合成数nに対して、少なくとも半分のaがnの合成数性を検出します。したがって、 k回の繰り返しでエラーの確率は最大で 2 ^{− k}に低減され、 k を増やすことで任意に小さくすることができます。

ランダム化素数判定法の基本的な構造は以下のとおりです。

1. ランダムに数字aを選びます。
2. （選択したテストに対応する）aと与えられた数nとの等式をチェックします。等式が成り立たない場合、nは合成数であり、aは合成数であることの証拠となり、テストは終了します。
3. 必要な精度に達するまで、手順1に戻ってください。

1回以上の反復の後、nが合成数でないことが判明した場合、nはおそらく素数であると宣言できます。

20 世紀初頭近く、フェルマーの小定理の系が素数判定に使えることが示されました。^{[ 9 ]}これにより、ポックリントン素数判定法が生まれました。^{[ 10 ]}しかし、この判定法はn − 1の部分因数分解を必要とするため、最悪の場合の実行時間はかなり遅いものでした。素朴な方法よりも大幅に高速な最初の決定論的素数判定法は、円分割判定法でした。その実行時間はO ((log n ) ^{c log log log n} )であることが証明できます。ここで、 nは素数判定する数、c はnに依存しない定数です。さらにいくつかの改良が加えられましたが、いずれも実行時間が多項式時間であることが証明できませんでした。 (実行時間は入力のサイズで測定され、この場合、入力サイズは ~ log nであり、これは数nを表すのに必要なビット数です。)解析的整数論に関するいくつかの予想が正しい場合、楕円曲線素数判定は O((log n ) ⁶ )で実行できることが証明できます。同様に、一般化リーマン予想(ミラーは紛らわしいことに「拡張リーマン予想」と呼んでいます) の下では、確率的ミラー・ラビン判定の基礎となる決定論的ミラー判定はÕ ((log n ) ⁴ ) で実行できることが証明できます。^{[ 11 ]}実際には、このアルゴリズムは、そもそも処理できる数のサイズに対して、他の 2 つのアルゴリズムよりも遅くなります。これら 2 つの方法の実装はかなり難しく、プログラミング エラーのリスクを生み出すため、遅くても単純な判定が好まれることがよくあります。          

2002年、Manindra Agrawal、Neeraj Kayal、Nitin Saxenaによって、証明可能な無条件の決定論的多項式時間素数判定法が初めて考案されました。AKS素数判定法はÕ((log n ) ¹² )で実行されます（彼らの論文の改訂版ではÕ((log n ) ^7.5 ) ^{[ 12 ]}に改善されています）。Sophie Germain予想が正しい場合は、さらにÕ((log n ) ⁶ )に短縮できます。 ^{[ 13 ]}その後、LenstraとPomeranceは、無条件でÕ((log n ) ⁶ )の時間で実行される判定法のバージョンを発表しました。^{[ 14 ]}    

アグラワル、カヤル、サクセナは、アグラワルの予想が正しい場合、彼らのアルゴリズムの変種が Õ((log n ) ^{3 ) で実行されることを提案している。しかし、ヘンドリック・レンストラとカール・ポメランスによるヒューリスティックな議論は、それがおそらく偽であることを示唆している。 [ 12 ]}アグラワルの予想の修正版であるアグラワル・ポポヴィッチ予想^{[ 15 ]}は、依然として正しい可能性がある。 

計算複雑性理論において、素数に対応する形式言語はPRIMESと表記される。PRIMESがCo-NPに属することは容易に証明できる。その補集合であるCOMPOSITESはNPに属する。なぜなら、因数を非決定論的に推測することで合成性を判定できるからである。

1975年、ヴォーン・プラットは、素数判定のための証明書が多項式時間で検証可能であることを示し、それによってPRIMESがNPに属し、したがって${\displaystyle {\mathsf {NP\cap coNP}}}$詳細は素数証明書を参照してください。

その後、Solovay–StrassenアルゴリズムとMiller–Rabinアルゴリズムが発見され、PRIMESはcoRPに含まれるようになった。1992年、Adleman–Huangアルゴリズム^{[ 7 ]}により複雑さは⁠に削減された。${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$これはプラットの結果を上回った。

1983年のアドルマン・ポメランス・ルーメリー素数判定法は、PRIMESをQP（準多項式時間）に分類したが、これは上述のクラスと比較できるものではないことが知られている。

実用上の扱いやすさ、リーマン予想を仮定した多項式時間アルゴリズム、その他の同様の証拠から、素数判定は多項式時間で解けるのではないかと長い間疑われていたが、証明されていなかった。AKS素数判定法の存在により、この長年の疑問はついに解決され、PRIMESはPに位置づけられた。しかし、PRIMESがP完全であるとは知られておらず、 NCやLなどPに含まれるクラスに属するかどうかも知られていない。PRIMESがAC ⁰に含まれないことは知られている。^{[ 16 ]}

ルーカス判定法やプロス判定法など、ある数が素数かどうかを判定するための数論的な方法が存在する。これらの判定法は通常、n  +  1、n − 1、または同様の数の因数分解を必要とするため、一般的な素数判定には適さないが、判定対象の数nが特定の形式であることが分かっている場合には非常に有効であることが多い。

ルーカス判定法は、素数nに対して、aがnを法とする原始根である場合、aのnを法とする乗法位数がn -1になるという事実に基づいています。aがnに対して原始根であることを示せれば、nが素数であることを示すことができます。

• archive.todayの非推奨リンク(2012年12月20日アーカイブ) – Maple での Solovay-Strassen 素数判定法の実装
• 素数と合成数の区別について、DJ Bernstein (cr.yp.to) 著
• プライムページ（primes.utm.edu）
• 因数分解されたN  − 1を用いたルーカス素数判定法 (MathPages.com)、米国議会図書館ウェブアーカイブ(2010年8月6日アーカイブ)
• PRIMABOINCAは、インターネットに接続されたコンピュータを使用して、いくつかの予想に対する反例を探す研究プロジェクトです。最初の予想（アグラワル予想）は、多項式時間で動作する最初の決定論的素数判定アルゴリズム（ AKSアルゴリズム）の定式化の基礎となりました。