素数判定テスト

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

最も簡単な素数判定は試し割りです。入力数 が与えられたとき、それが2 から までの任意の素数で割り切れるかどうか（つまり、割り算で余り が残らないかどうか）を調べます。 できる場合、 は合成数です。 それ以外の場合、 は素数です。^[1]任意の約数 に対して、別の約数 との素約数が存在するはずなので、最大で の素約数を探せば十分です。 ${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle n}$${\displaystyle p\geq {\sqrt {n}}}$${\displaystyle n/p\leq {\sqrt {n}}}$${\displaystyle q}$${\displaystyle n/p}$${\displaystyle {\sqrt {n}}}$

たとえば、100 という数を考えてみましょう。100 の約数は、次の数です。

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

までのすべての約数をテストすると、いくつかの約数は2 回発見されます。これを観察するには、100 の約数のペアのリストを考えます。 ${\displaystyle n}$

${\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}$。

過去の積は、それ以前に現れた積の逆です。たとえば、と は互いに逆です。さらに、2 つの約数とについても逆です。この観察結果はすべての に一般化されます。 のすべての約数ペアにはより小さいか等しい約数が含まれるため、アルゴリズムは より小さいか等しい約数を検索するだけで、すべての約数ペアを確実に検出できます。^[1]${\displaystyle 10\times 10}$${\displaystyle 5\times 20}$${\displaystyle 20\times 5}$${\displaystyle 5\leq {\sqrt {100}}=10}$${\displaystyle 20\geq {\sqrt {100}}=10}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

また、2 は 100 を割り切る素数であり、これは 100 が素数でないことを直ちに証明します。算術の基本定理により、1 を除くすべての正の整数は少なくとも 1 つの素数で割り切れます。したがって、アルゴリズムはより小さいか に等しい素因数を検索するだけで済みます。 ${\displaystyle {\sqrt {n}}}$

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

素数のリストを計算するのが現実的でない場合は、単純に（そしてゆっくりと）との間のすべての数を約数としてチェックすることもできます。 単純な最適化は、 を 2 で割り切れるか、および 3 と の間の奇数だけで割り切れるかをテストすることです。これは、偶数で割り切れるということは 2 で割り切れることを意味するためです。 ${\displaystyle \leq {\sqrt {n}}}$${\displaystyle 2}$${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

この方法はさらに改良することができます。 3 より大きいすべての素数は、非負整数および に対しての形をしていることに注意してください。実際、すべての整数は、正の整数およびに対して の形をしています。 2 は、および を割り切り、3 は 、および を割り切るので、3 より大きい素数に対して 6 を法とする唯一の剰余は 1 と 5 です。したがって、 のより効率的な素数判定は、 が 2 または 3 で割り切れるかどうかを判定してから、 および の形式を持つすべての数を調べて であるかどうかを調べることです。これは、 までのすべての数を判定するよりもほぼ 3 倍高速です。 ${\displaystyle 6k+i}$${\displaystyle k}$${\displaystyle i\in \{1,5\}}$${\displaystyle 6k+i}$${\displaystyle k}$${\displaystyle i\in \{0,1,2,3,4,5\}}$${\displaystyle 6k,6k+2}$${\displaystyle 6k+4}$${\displaystyle 6k}$${\displaystyle 6k+3}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 6k+1}$${\displaystyle 6k+5}$${\displaystyle \leq {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

さらに一般化すると、 ( c 素数)より大きいすべての素数は、正の整数に対しての形をとり、 と互いに素です。たとえば、 を考えます。 となる整数に対して、すべての整数は の形をとります。ここで、2 は を割り切れ、3 は を割り切れ、5 は を割り切れます。したがって、30 より大きいすべての素数はに対しての形をとります。もちろん、と互いに素である形の数すべてが素数であるわけではありません。たとえば、17 は と互いに素ですが、 は素数ではありません。 ${\displaystyle c\#}$${\displaystyle c\#\cdot k+i}$${\displaystyle i,k}$${\displaystyle 0\leq i<c\#}$${\displaystyle i}$ ${\displaystyle c\#}$${\displaystyle 6\#=2\cdot 3\cdot 5=30}$${\displaystyle 30k+i}$${\displaystyle i,k}$${\displaystyle 0\leq i<30}$${\displaystyle 0,2,4,\dots ,28}$${\displaystyle 0,3,6,\dots ,27}$${\displaystyle 0,5,10,\dots ,25}$${\displaystyle 30k+i}$${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$${\displaystyle c\#\cdot k+i}$${\displaystyle i}$${\displaystyle c\#}$${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7}$

が大きくなるにつれて、互いに素な余りの余りに対する割合が減少するため、テストにかかる時間が短縮されます (ただし、 未満のすべての素数で割り切れるかどうかをチェックする必要はあります)。前述と同様の観察は再帰的に適用でき、エラトステネスのふるい が得られます。 ${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$

これらの方法 (および以下で説明する他のすべての方法) を高速化する 1 つの方法は、200 までのすべての素数など、特定の境界までのすべての素数のリストを事前に計算して保存することです。(このようなリストは、エラトステネスのふるいを使用して計算するか、各増分をすべての既知の素数に対してテストするアルゴリズムによって計算できます。) 次に、大規模な方法で素数かどうかをテストする前に、まずリスト内の任意の素数で割り切れるかどうかを確認します。それらの数のいずれかで割り切れる場合は合成数であり、それ以降のテストはスキップできます。 ${\displaystyle m}$${\displaystyle \leq {\sqrt {m}}}$${\displaystyle n}$${\displaystyle n}$

単純ですが非常に非効率的な素数判定には、ウィルソンの定理を使用します。これは、次の場合にのみ が素数であると規定する定理です。 ${\displaystyle p}$

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

この方法はモジュラー乗算を必要とするため実用的ではありませんが、素数とモジュラー剰余に関する定理は、より多くの実用的な方法の基礎を形成します。 ${\displaystyle p}$

これらは、実際にはうまく機能するように見えるテストですが、証明されていないため、技術的に言えばアルゴリズムではありません。フェルマー テストとフィボナッチ テストは簡単な例であり、組み合わせると非常に効果的です。ジョン セルフリッジは、 pが奇数で、p ≡ ±2 (mod 5) の場合、次の両方が成り立つと 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 ( 1 ) _{p +1} ≡ 0 (mod p )、

f ( x ) _{k は}xにおけるk次のフィボナッチ多項式です。

セルフリッジ、カール・ポメランス、サミュエル・ワグスタッフは、反例に対して合計620ドルを提示した。^[2]

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

ランダム化素数判定テストの基本構造は次のとおりです。

1. ランダムに数字a を選びます。
2. aと指定された数nの等式 (選択したテストに対応) を確認します。等式が成立しない場合は、n は合成数であり、a は合成数の証拠であり、テストは停止します。
3. 必要な精度が達成されるまで、ステップ 1 に戻ります。

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

最も単純な確率的素数判定は、フェルマー素数判定(実際は合成性判定) です。これは次のように機能します。

整数n が与えられたとき、nと互いに素な整数a を選択し、nを法とするa ^{n − 1}を計算します。結果が 1 と異なる場合、n は合成数です。結果が 1 の場合、n は素数である可能性があります。

a ^{n −1} ( nを法として) が 1 だがnが素数でない場合、 n はa を底とする擬素数と呼ばれます 。実際には、 a ^{n −1} ( nを法として) が 1 の場合、n は通常素数です。しかし、反例があります。n = 341 でa = 2 の場合、

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

341 = 11·31は合成数ですが、実際には341は2を底とする最小の擬素数です（ ^[3]の図1を参照）。

2.5 × 10未満の2を底とする擬素数は21853個しかない。^{10 （ [3]}の1005ページを参照）。これは、 nが2.5 × 10までの^10、2 n ⁻¹ ( nを法として) が 1 に等しい場合、 n^は素数です。ただし、 n がこれらの 21853 個の擬似素数のいずれかでない場合は除きます。

いくつかの合成数（カーマイケル数）は、 nと互いに素なすべてのaに対して、 a ^{n − 1}は 1（nを法として）であるという性質を持っています。最小の例はn = 561 = 3·11·17 で、この場合、 561 と互いに素なすべてのaに対して、 a ⁵⁶⁰は 1（ 561 を法として）です。しかし、フェルマーテストは、たとえばRSA 公開鍵暗号化アルゴリズムの鍵生成フェーズなど、数を迅速にスクリーニングする必要がある場合によく使用されます。

ミラー・ラビン素数判定とソロベイ・シュトラッセン素数判定はより洗練された変種であり、すべての合成数を検出します（もう一度言いますが、これは次のことを意味します。すべての合成数nについて、少なくとも 3/4 (ミラー・ラビン) または 1/2 (ソロベイ・シュトラッセン) の数a がnの合成数の証拠となります）。これらも合成数判定です。

ミラー・ラビン素数判定は次のように行われます。整数nが与えられたとき、正の整数a  <  nを選択します。2 ^s d = n  − 1とします（dは奇数）。

${\displaystyle a^{d}\not \equiv \pm 1{\pmod {n}}}$

そして

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$全ての${\displaystyle 0\leq r\leq s-1,}$

ならばnは合成数であり、aは合成数の証拠となる。そうでない場合、nは素数かもしれないし、そうでないかもしれない。ミラー・ラビンテストは強力な素数確率テストである（PSW ^[3] 1004ページを参照）。

ソロベイ・シュトラッセン素数判定では別の等式が用いられる。奇数nが与えられたとき、 a  <  nである整数aを選ぶ。

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$、ヤコビ記号はここにあります、${\displaystyle \left({\frac {a}{n}}\right)}$

ならばnは合成数であり、aは合成数の証拠となる。そうでない場合、nは素数かもしれないし、そうでないかもしれない。ソロベイ・シュトラッセンテストはオイラー確率素数テストである（PSW ^[3] 1003ページを参照）。

aの各値に対して、ソロベイ・シュトラッセン検定はミラー・ラビン検定よりも弱い。例えば、n = 1905 でa = 2 の場合、ミラー・ラビン検定ではnが合成数であることが示されるが、ソロベイ・シュトラッセン検定では示されない。これは、1905 が 2 を底とするオイラー擬素数ではあるが、2 を底とする強い擬素数ではないためである（これは PSW ^[3]の図 1 に示されている）。

ミラー・ラビン素数判定とソロベイ・シュトラッセンの素数判定は単純で、他の一般的な素数判定よりもはるかに高速です。場合によっては、効率をさらに向上させる方法の 1 つにフロベニウス擬素数判定があります。このテストの 1 ラウンドはミラー・ラビンの 1 ラウンドの約 3 倍の時間がかかりますが、ミラー・ラビンの 7 ラウンドに匹敵する確率境界を達成します。

フロベニウス テストは、ルーカスの素数確率テストを一般化したものです。

ベイリー-PSW素数判定テストは、フェルマーまたはミラー-ラビンテストとルーカスの確率的素数判定テストを組み合わせた確率的素数判定テストであり、反例が知られていない素数判定テストを実現します。つまり、このテストでnがおそらく素数であると報告される合成数nは知られていません。^{[4] [5]} nには反例がないことが示されている。 ${\displaystyle <2^{64}}$

Leonard AdlemanとMing-Deh Huangは、楕円曲線素数判定テストのエラーのない（ただし多項式時間であることが予想される）変種を発表しました。他の確率的テストとは異なり、このアルゴリズムは素数証明を生成するため、数が素数であることを証明するために使用できます。^[6]このアルゴリズムは実際には法外に遅いです。

量子コンピュータが利用可能であれば、素数性の判定は古典コンピュータを使用するよりも漸近的に高速に行うことができる。整数因数分解法であるショアのアルゴリズムとポックリントン素数性判定法を組み合わせることで、の問題を解決できる可能性がある。^[7]${\displaystyle O((\log n)^{3}(\log \log n)^{2}\log \log \log n)}$

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

2002年、マニンドラ・アグラワル、ニーラジ・カヤル、ニティン・サクセナによって、最初の証明可能無条件の決定論的多項式時間素数判定が発明された。AKS素数判定はÕ((log  n ) ¹² )で実行される（彼らの論文の公開された改訂版では Õ((log  n ) ^7.5 ) ^{[11]に改良されている）。これは}ソフィー・ジェルマン予想が正しい場合、さらにÕ((log n ) ⁶ )に短縮できる。^{[12]その後、レンストラとポメランスは、無条件にÕ((log} n ) ⁶ )の時間で実行されるバージョンの判定を発表した 。 ^[13]

アグラワル、カヤル、サクセナは、アグラワルの予想が正しい場合、 Õ((log  n ) ³ )で実行されるアルゴリズムの変形を提案している。しかし、ヘンドリック・レンストラとカール・ポメランスによる経験的議論は、それがおそらく誤りであることを示唆している。 ^[11]アグラワルの予想の修正版であるアグラワル・ポポヴィッチ予想^[14]は、依然として正しい可能性がある。

計算複雑性理論では、素数に対応する形式言語は PRIMES と表記されます。PRIMES がCo-NPに属することは簡単に示せます。その補数である COMPOSITES はNPに属します。これは、非決定論的に因数を推測することで合成数を決定できるためです。

1975 年、ヴォーン・プラットは、多項式時間で検証可能な素数証明が存在し、したがって PRIMES はNPに含まれ、したがって⁠ ⁠${\displaystyle {\mathsf {NP\cap coNP}}}$に含まれることを示しました。詳細については素数証明を参照してください。

その後のSolovay-StrassenアルゴリズムとMiller-Rabinアルゴリズムの発見により、PRIMESはcoRPに収束しました。1992年には、Adleman-Huangアルゴリズム^{[6]によって}計算量が⁠ ⁠${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$にまで削減され、Prattの結果に取って代わりました。

1983 年の Adleman–Pomerance–Rumely 素数判定テストでは、PRIMES は QP (準多項式時間) に分類されましたが、これは上記のクラスと比較できるかどうかはわかっていません。

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

ルーカス テストやプロス テストなど、数が素数であるかどうかをテストするための数論的手法がいくつかあります。これらのテストでは通常、n  + 1、n − 1、または同様の量の因数分解が必要になるため、汎用的な素数判定には役立ちませんが、テスト対象の数n が特殊な形式であることがわかっている 場合は、非常に強力になることがよくあります。

ルーカス テストは、 a がn を法とする原始根である場合、 n を法とする数aの乗法順序は素数nに対してn − 1であるという事実に依存します。 a がnに対して原始的であることを示すことができれば、 nが素数であることを示すことができます。

Wikifunctions にはこのトピックに関連する機能があります。

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