Loading article…
数論において、確率素数（PRP）とは、すべての素数が満たす特定の条件を満たすが、ほとんどの合成数は満たさない整数のことである。確率素数の種類によって、満たすべき特定の条件は異なる。合成数である確率素数（擬似素数と呼ばれる）も存在する可能性があるが、一般的には、そのような例外が稀になるように条件が設定されている。
フェルマーの小定理に基づく合成数判定法は、次のように機能します。整数nが与えられたとき、 nの倍数ではない整数aを選びます(通常、1 < a < n − 1の範囲でaを選びます)。n を法とする a n − 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⁹未満のものは 11347 個あります。[ 1 ] : 1005
フェルマー判定法は、素数を法とする1の平方根が1と-1のみであるという事実を利用することで、別の方法で改善できる。n = d · 2s + 1と書く。ただしdは奇数である。数nがaを基数とする強い確率素数（SPRP）であるのは、次の条件を満たす場合である。
または
基数aに対する合成強確率素数を、基数aに対する強擬素数と呼ぶ。基数aに対するすべての強確率素数は、同じ基数に対するオイラー確率素数でもあるが、その逆は成り立たない。
ルーカス数列に基づくルーカス確率素数も存在する。ルーカス確率素数判定法は単独で使用できる。ベイリー-PSW素数判定法は、ルーカス判定法と強力な確率素数判定法を組み合わせたものである。
97が2進数の素数である可能性が高いかどうかをテストするには：
