ミラー–ラビン素数判定法
以下に Ruby での本アルゴリズムの実施例を示す。
かつ、任意の 0 ≤ r ≤ s − 1 {\displaystyle 0\leq r\leq s-1} に対して
a 2 r d ≢ − 1 ( mod n ) {\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}
すると、n は合成数であり、a は n の合成性の証拠(証人)である。証拠とならない a を「強い嘘つき; strong liar」と呼び、n を底 a についての「強擬素数; strong pseudoprime」と呼ぶ。「強い嘘つき」とは、n が合成数であるのに合同式が成立することによって素数であると嘘をつくことから来ている。
奇数の合成数には、多くの証拠(証人)a がある。しかし、そのような a を生成する単純な方法は知られていない。ミラー–ラビン素数判定法では、 a ∈ ( Z / n Z ) {\displaystyle a\in \left(\mathbb {Z} /n\mathbb {Z} \right)} であるような数をランダムに選択し、それが n の合成性の証拠(証人)となりうるかを調べる。n が合成数なら、ほとんどの a は証拠となるので、高い確率で n が合成数であることを検出できる。しかし、不運にも n に対する「強い嘘つき」となる a を選んでしまう可能性も若干ある。この確率を減らすには、いくつかの独立に選んだ a で判定を繰り返す。