確率的素数
確率的素数の性質は効率的な素数判定アルゴリズムの基礎であり、これは暗号理論に応用されている。これらのアルゴリズムは通常本質的に確率的である。任意の固定したaに対してaを底とする合成数の確率的素数がある一方、任意の合成数nに対して任意にaを選択した場合nが底aに対して擬素数である確率が最大Pであるような決まったP<1が存在することを期待することができる。この判定法をk回繰り返し、毎回新たなaを選ぶと、判定した全てのaに対してnが擬素数である確率は最大Pであり、これは指数関数的に減少するため、この確率を無視できるほど小さくするためには適度なkのみが必要である(例えばコンピュータハードウェアのエラーの確率と比較して)。
カーマイケル数が存在するため、このことは弱い確率的素数については残念ながら間違いである。ただし、強い確率的素数(P = 1/4, ミラー-ラビン素数判定法)やオイラー確率的素数(P = 1/2, ソロベイ-シュトラッセン素数判定法)などより洗練された確率的素数の概念にはあてはまる。
決定的素数の証明が必要な場合であっても、有用な最初の段階は確率的素数を判定することである。これによりほとんどの合成数を(確実に)迅速に取り除くことができる。
PRP判定は、いくつかのしきい値よりも小さい数の素数性を迅速に確立するために、小さな擬素数の表と組み合わされることがある。