ミラー–ラビン素数判定法
a d ≠ 1 mod n {\displaystyle a^{d}\neq 1\ {\bmod {\ }}n} で、かつ [ 0 , s − 1 {\displaystyle [0,s-1\ } ] の範囲の全ての r {\displaystyle r} について a 2 r d mod n ≠ − 1 {\displaystyle a^{{2^{r}}d}\ {\bmod {\ }}n\neq \ -1} なら、composite を返す。
probably prime を返す。
平方の繰り返しをべき剰余を使って実現すると、このアルゴリズムの実行時間は O(k × log n) となる。ここで、k は異なる a で判定を行う回数である。以上から、このアルゴリズムが多項式時間の効率のよいアルゴリズムであることがわかる。FFTベースの乗算によって実行時間を Õ(k × log n) まで抑えることができる。
ミラー–ラビン素数判定法は、Gary L. Miller が最初に開発したMillerテストをマイケル・ラビンが無条件の確率的アルゴリズムに修正したものである。元となったMillerテストはある限度以下の全ての a を調べるという、未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムである。とはいえ拡張リーマン予想全体を必要とするわけではなく、平方ディリクレ指標について拡張リーマン予想が成り立てばよい。
Millerテストは未証明の拡張リーマン予想を必要としていることや、それを修正したミラー–ラビン素数判定法が許容出来る誤判定確率から判定時間を調整でき速度面で有利であることから実際には使われていない。また同じく決定的アルゴリズムであるAKS素数判定法の方が、証明されていない予想に依存していないぶんだけMillerテストよりも強い。
Millerテストには、判定を信頼できるものにするには限度をどう決めたらよいかという問題がある。
判定対象の数 n が合成数なら、n と互いに素な「強い嘘つき」の a は群 ( Z / n Z ) ∗ {\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}} の真の部分群に含まれる。つまり ( Z / n Z ) ∗ {\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}} の生成元集合の全 a について判定するとき、その中には必ず n の合成性の証拠となる数が含まれる。