ミラー–ラビン素数判定法

ミラー–ラビン素数判定法（）またはラビン–ミラー素数判定法（）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。
概念.
フェルマーやソロベイ–シュトラッセンの素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。
まず、有限体 formula_1 の単位元の平方根についての補題を考える。ここで、"p" は奇素数である。"p" を法とした剰余（mod "p"）において、1と-1の二乗は常に1となる。これらを 1 の「自明な」平方根と呼ぶ。"p" は素数なので 1 の「自明でない」平方根は存在しない。これを示すため、1 mod "p" の非自明な平方根を "x" とする。このとき、以下が成り立つ:
"p"は素数なので、これはformula_5 または formula_6 が "p"で割り切れることを示す。一方、"x" は 1 でも -1 でもないので(mod "p")、 formula_5 も formula_6 も "p" で割り切れない。すなわち、二乗して 1 (mod "p"）となるのは、1 および -1 だけということになる。
さて、"n" を" n > 2" の奇数としたとき、"n" − 1 を formula_9 と表現できる。ここで "s" は正整数で、"d" は奇数である。つまり、"d" は "n" − 1 を繰り返し 2 で割った結果と同じである。すると、全ての formula_10 について:
または、ある formula_12 に対して
が成立する。
これらのいずれかが真となることを示すため、以下のフェルマーの小定理を利用する:
ここで、
であるから、この平方根は上述の補題から 1 または −1 （mod "n"）である。−1 の場合は後者の合同式が成り立つ。
1 の場合はさらに平方根を考えていくと、上述の補題から 1 または −1 （mod "n"）となる。一度も −1 （mod "n"）とならないまま、"r" = 0 となったとする。
この場合後者の合同式は成立せず、前者の合同式が成立する。
ミラー-ラビン素数判定法は上記の主張の対偶に基づいている。すなわち、整数 "n" に対し、以下が成り立つ "a" を見つけたとする。
かつ、任意の formula_18 に対して
すると、"n" は合成数であり、"a" は "n" の合成性の証拠（証人）である。証拠とならない "a" を「強い嘘つき; strong liar」と呼び、"n" を底 "a" についての「強擬素数; strong pseudoprime」と呼ぶ。「強い嘘つき」とは、"n" が合成数であるのに合同式が成立することによって素数であると嘘をつくことから来ている。
奇数の合成数には、多くの証拠（証人）"a" がある。しかし、そのような "a" を生成する単純な方法は知られていない。ミラー-ラビン素数判定法では、formula_20 であるような数をランダムに選択し、それが "n" の合成性の証拠（証人）となりうるかを調べる。"n" が合成数なら、ほとんどの "a" は証拠となるので、高い確率で "n" が合成数であることを検出できる。しかし、不運にも "n" に対する「強い嘘つき」となる "a" を選んでしまう可能性も若干ある。この確率を減らすには、いくつかの独立に選んだ "a" で判定を繰り返す。
アルゴリズムと実行時間.
このアルゴリズムは次のように表現される: