素数の可能性

数論において、確率素数( PRP ) とは、すべての素数が満たすが、ほとんどの合成数が満たさない特定の条件を満たす整数です。確率素数の種類によって特定の条件は異なります。合成数である確率素数 (擬素数と呼ばれる) が存在する場合もありますが、このような例外がまれになるように条件が選択されるのが一般的です。

フェルマーの合成数テストは、フェルマーの小定理に基づいており、次のように機能します。整数nが与えられたときに、 nの倍数ではない整数a を選択します(通常、aは1 < a < n − 1 の範囲で選択します)。nを法としてa ^{n − 1}を計算します。結果が 1 でない場合、nは合成数です。結果が 1 の場合、nは素数である可能性が高く、n はa を底とする確率的素数と呼ばれます。a を底とする弱い確率的素数とは、 a を底とする確率的素数である整数ですが、 a を底とする強い確率的素数ではない整数です(以下を参照)。

固定された底aに対して、合成数がその底の確率的に素数（つまり擬素数）になることは珍しい。例えば、25 × 10 ⁹まで、奇数の合成数は 11,408,012,595 個あるが、底が 2 の擬素数は 21,853 個しかない。 ^{[1] : 1005}同じ間隔内の奇数の素数の数は 1,091,987,404 個である。

確率的素数性は、効率的な素数判定 アルゴリズムの基礎であり、暗号化に応用されています。これらのアルゴリズムは通常、本質的に確率的です。その考え方は、任意の固定されたaに対してa を底とする合成素数が存在する一方で、任意の合成数 n に対して a をランダムに選択した場合に、 n が a を底とする疑似素数である確率が最大で P となるような、固定された P < 1 が存在することを期待できるというものです。このテストをk回繰り返し、そのたびに新しいa を選択すると、テストされたすべてのaに対してnが疑似素数である確率は最大でP ^kとなり、この確率は指数的に減少するため、この確率を無視できるほど小さくするために必要なkは中程度です (たとえば、コンピュータ ハードウェア エラーの確率と比較して)。

残念ながら、弱い確率素数の場合はカーマイケル数が存在するため、これは誤りです。しかし、強い確率素数 ( P  = 1/4、ミラー・ラビンアルゴリズム) やオイラー確率素数 ( P  = 1/2、ソロベイ・シュトラッセンアルゴリズム) など、確率素数のより洗練された概念の場合は当てはまります。

決定論的な素数性の証明が必要な場合でも、最初のステップとして、素数である可能性をテストすることが役立ちます。これにより、ほとんどの合成数を素早く（確実に）排除できます。

PRP テストは、小さな擬素数の表と組み合わせて、あるしきい値よりも小さい特定の数値の素数をすばやく判定することがあります。

a を底とするオイラー確率素数 は、任意の素数 pに対して、a ^{( p −1)/2 は}p を法として等しいというやや強い定理によって素数と示される整数である。ここで、はヤコビ記号である。合成数であるオイラー確率素数は、a を底とする オイラー・ヤコビ擬素数と呼ばれる。2 を底とする最小のオイラー・ヤコビ擬素数は 561 である。^{[1] : 1004  25·10 9}未満の 2 を底とするオイラー・ヤコビ擬素数は 11347 個ある。^{[1] : 1005}${\displaystyle ({\tfrac {a}{p}})}$${\displaystyle ({\tfrac {a}{p}})}$

このテストは、素数を法とする 1 の平方根は 1 と -1 だけであるという事実を利用することで改善できます。n  =  d  · 2 ^s  + 1 と書きます。ここで、dは奇数です。次の条件を満たす場合、数nはa を底とする強確率素数( SPRP )です。

${\displaystyle a^{d}\equiv 1{\pmod {n}},\;}$

または

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ ある }}0\leq r\leq s-1.\,}$

a を底とする合成の強確率素数は、a を底とする強擬素数と呼ばれます。a を底とするすべての強確率素数は、同じ底のオイラー確率素数でもありますが、その逆は当てはまりません。

2を底とする最小の強擬素数は2047である。^{[1] : 1004  25·10 9}未満の2を底とする強擬素数は4842個ある。^{[1] : 1005}

ルーカス数列に基づくルーカス確率素数もあります。ルーカス確率素数テストは単独でも使用できます。ベイリー-PSW 素数性テストは、ルーカス テストと強い確率素数テストを組み合わせたものです。

97 が 2 を底とする強い素数であるかどうかをテストするには:

• ステップ1:および を求めます。ただし は奇数です。 ${\displaystyle d}$${\displaystyle s}$${\displaystyle 96=d\cdot 2^{s}}$${\displaystyle d}$
  • から始まると、${\displaystyle s=0}$${\displaystyle d}$${\displaystyle 96}$
  • が増加すると、およびが増加することがわかります。${\displaystyle s}$${\displaystyle d=3}$${\displaystyle s=5}$${\displaystyle 96=3\cdot 2^{5}}$
• ステップ 2: を選択します。を選択します。${\displaystyle a}$${\displaystyle 1<a<97-1}$${\displaystyle a=2}$
• ステップ3:を計算します。これは と合同ではないので、次の条件をテストし続けます。${\displaystyle a^{d}{\bmod {n}}}$${\displaystyle 2^{3}{\bmod {9}}7}$${\displaystyle 1}$
• ステップ4:を計算します。 が と合同であれば、はおそらく素数です。 そうでなければ、は間違いなく合成数です 。${\displaystyle 2^{3\cdot 2^{r}}{\bmod {9}}7}$${\displaystyle 0\leq r<s}$${\displaystyle 96}$${\displaystyle 97}$${\displaystyle 97}$
  • ${\displaystyle r=0:2^{3}\equiv 8{\pmod {97}}}$
  • ${\displaystyle r=1:2^{6}\equiv 64{\pmod {97}}}$
  • ${\displaystyle r=2:2^{12}\equiv 22{\pmod {97}}}$
  • ${\displaystyle r=3:2^{24}\equiv 96{\pmod {97}}}$
• したがって、は 2 を底とする強い素数です (したがって、2 を底とする強い素数です)。${\displaystyle 97}$

• 証明可能な素数
• ベイリー-PSW素数判定
• オイラー・ヤコビ擬素数
• ルーカス擬素数
• ミラー・ラビン素数判定
• ペラン素数判定
• カーマイケル数

• 素数用語集 – 推定素数
• PRPトップ10000（最大の既知の素数）