ミラー–ラビン素数判定法
例えば、Jaeschke (1993) は以下を検証した。
もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。
もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。
もちろん、a < n の場合だけ調べる。この種の基準については を参照されたい。このような結果を活用することで、ある範囲の数については非常に高速で決定的な素数判定が可能である。
しかし、全ての合成数についてはこのような有限の集合では不十分である。Alford、Granville、Pomerance は、合成数 n について合成性の証拠となる最小の数が ( ln  n ) 1 / ( 3 ln  ln  ln  n ) {\displaystyle (\ln n)^{1/(3\ln \ln \ln n)}\;} より大きい合成数が無数に存在する、X が十分大きいときには X 以下のそのような合成数の個数は少なくとも X 1 / ( 35 ln  ln  ln  X ) {\displaystyle X^{1/(35\ln \ln \ln X)}} であることを示した。また彼らはヒューリスティック的に、w 以下の合成性の証拠となる数のある n 以下の合成数について w のオーダーを Θ ( ln  n ln  ln  n ) {\displaystyle \Theta (\ln n\,\ln \ln n)} であると示唆した。
pは素数なので、これは x − 1 {\displaystyle x-1} または x + 1 {\displaystyle x+1} が pで割り切れることを示す。一方、x は 1 でも -1 でもないので(mod p)、 x − 1 {\displaystyle x-1} も x + 1 {\displaystyle x+1} も p で割り切れない。すなわち、二乗して 1 (mod p)となるのは、1 および -1 だけということになる。
さて、n を n > 2 の奇数としたとき、n − 1 を 2 s ⋅ d {\displaystyle 2^{s}\cdot d} と表現できる。ここで s は正整数で、d は奇数である。つまり、d は n − 1 を繰り返し 2 で割った結果と同じである。すると、全ての a ∈ ( Z / n Z ) ∗ {\displaystyle a\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}} について:
a d ≡ 1 ( mod n ) {\displaystyle a^{d}\equiv 1{\pmod {n}}}
または、ある 0 ≤ r ≤ s − 1 {\displaystyle 0\leq r\leq s-1} に対して
a 2 r ⋅ d ≡ − 1 ( mod n ) {\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}
ミラー–ラビン素数判定法(英: Miller–Rabin primality test)またはラビン–ミラー素数判定法(英: Rabin–Miller primality test)は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。