確率的素数

数論において、確率的素数（probable prime, PRP）は、ほとんどの合成数は満たさないが全ての素数が満たす特定の条件を満たす整数。確率的素数には様々な条件がある。合成数である確率的素数（擬素数と呼ばれる）が存在する可能性があるが、一般的にはこのような例外を少なくするために条件が選ばれる。
フェルマーの小定理に基づくフェルマーの合成数判定は次のように進む。整数"n"が与えられ、"n"の倍数ではない整数"a"をいくつか選び出す（通常はの範囲で"a"を選ぶ）。を計算する。結果が1でない場合、"n"は合成数である。結果が1である場合、"n"は素数である可能性がある。"n"はこのときa"を底とする確率的素数という。a"を底とする弱い確率的素数は"a"を底とする確率的素数であるが、"a"を底とする強い確率的素数ではない整数のことである（以下参照）。
決まった底"a"の場合、合成数がその底で確率的素数（つまり擬素数）になることは珍しい。例えば、最大のとき、11,408,012,595個の奇数の合成数があるが、底が2の擬素数は21,853個のみである。同じ範囲にある奇数の素数の数は1,091,987,404である。
性質.
確率的素数の性質は効率的な素数判定アルゴリズムの基礎であり、これは暗号理論に応用されている。これらのアルゴリズムは通常本質的に確率的である。任意の固定した"a"に対して"a"を底とする合成数の確率的素数がある一方、任意の合成数"n"に対して任意に"a"を選択した場合"n"が底aに対して擬素数である確率が最大Pであるような決まった"P"&lt;1が存在することを期待することができる。この判定法を"k"回繰り返し、毎回新たな"a"を選ぶと、判定した全ての"a"に対して"n"が擬素数である確率は最大"Pk"であり、これは指数関数的に減少するため、この確率を無視できるほど小さくするためには適度な"k"のみが必要である（例えばコンピュータハードウェアのエラーの確率と比較して）。
カーマイケル数が存在するため、このことは弱い確率的素数については残念ながら間違いである。ただし、強い確率的素数（"P" = 1/4, ミラー-ラビン素数判定法）やオイラー確率的素数（"P" = 1/2, ソロベイ-シュトラッセン素数判定法）などより洗練された確率的素数の概念にはあてはまる。
決定的素数の証明が必要な場合であっても、有用な最初の段階は確率的素数を判定することである。これによりほとんどの合成数を（確実に）迅速に取り除くことができる。
PRP判定は、いくつかのしきい値よりも小さい数の素数性を迅速に確立するために、小さな擬素数の表と組み合わされることがある。
バリエーション.
底"a"のオイラー確率的素数は、任意の素数"p"に対して"a"("p" − 1)/2 = formula_1 (mod "p")（ここで formula_1 はヤコビ記号）というやや強い定理により素数と示される整数である。合成数であるオイラー確率的素数は、底"a"のオイラー・ヤコビ擬素数と呼ばれる。底2のオイラー・ヤコビ擬素数で最小のものは561である（の1004ページ参照）。25·109未満には底2のオイラー・ヤコビ擬素数は11347個ある（の1005ページ参照）。
この判定法は1を法とする素数の平方根が1と−1であるという事実を用いることで改善できる。"n" = "d" · 2"s" + 1（"d"は奇数）と書ける。"n"は、底"aとする"強い確率的素数(SPRP)である。
もしくは
底"a"の強い確率的素数で合成数であるものは、底"a"の強い擬素数と呼ばれる。全ての底"a"の強い確率的素数は同じ底のオイラー確率的素数でもあるが、逆は真ではない。
底2の強い擬素数で最小のものは2047である（の1004ページ参照）。25·109未満には底2の強い擬素数は4842個ある（の1005ページ参照）。
リュカ数列に基づくリュカ確率的素数もある。リュカ確率的素数判定は単独で使うことができる。Baillie-PSW素数判定法は、リュカ判定法と強い確率的素数判定法を組み合わせたものである。
SPRPの例.
97が底2の強い確率的素数かどうかを判定する。