素数の可能性

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

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

固定された基数aに対して、合成数がその基数に対して確率的に素数（つまり擬素数）となることは稀です。例えば、250億までの範囲で、奇数の合成数は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}^{2 を底とするオイラー・ヤコビ擬素数で 25·10 9}未満のものは 11347 個ある。^[1]^{: 1005} $({\tfrac {a}{p}})$ $({\tfrac {a}{p}})$

フェルマーテストは、素数を法とする1の平方根は1と-1の2つだけであるという事実を利用することで、より正確に求めることができます。n = d · 2 ^s + 1と書きます（dは奇数）。nがaを底とする強確率素数（SPRP）である場合、以下の条件を満たします。

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

または

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

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

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

強い素数の検定例

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

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