乱択アルゴリズム
n が合成数なら、n 未満の自然数の少なくとも4分の3は n の合成性の証拠である
n と k が与えられたとき、k が n の合成性の証拠かどうかを素早く判定するアルゴリズムがある
以上から、素数判定問題が Co-RP クラスであることを暗示していることがわかる。ある合成数 n より小さい100個のランダムに選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4) であり、多くの実用的な目的にはこれが十分によい素数判定となる。n が大きい場合、これ以外の実用的な素数判定法は存在しないだろう。間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。
従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが(AKS素数判定法)、暗号ソフトウェアでは未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。
決定問題LがZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズムAが存在し、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率も、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率も1であるときに言う。
NP困難問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、近似アルゴリズムが必要となる。
歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。当時、素数判定の実用的な決定的アルゴリズムは知られていなかった。
ミラー-ラビン素数判定法は、2つの正の整数 k と n について「k は n が合成数であることの証拠である」というような二項関係に基づいている。これをもう少し具体化すると、
n が合成数である証拠があるなら、n は合成数(素数でない)である