確率的素数判定法（フェルマーテスト）
$p$ が素数かどうかを確率的に判定するフェルマーテストは以下である．
(Step 0) 最大繰り返し回数を $k$ として，$n=1$ とする．
(Step 1) $x$ を適当に決める．
(Step 2) $y=x^{p-1} \bmod p$ を計算して，$y \ne 1$ ならば $p$ を「合成数」と判定して終了．
$y=1$ の場合，$n$$<$$k$ ならば $n\Leftarrow n+1$ として(Step 1)へ．
もし $n=k$ ならば，$p$ を「おそらく素数」と判定して終了．□
この判定法によって，素数でないにもかかわらず誤って「素数」と判定する確率は，$\frac{1}{4^n}$ 以下である．
$p=$
$x=$，
$n=$
$\Rightarrow$