ミラー・ラビン素数判定法
Miller–Rabin primality test
ミラー氏の方法をラビン氏が改良したものらしい。
仕組み
フェルマーの小定理
$ \forall p \in \mathbb{P} \quad \forall a \in \mathbb{Z} \quad a^{p-1} \equiv 1 \pmod p
と、
$ a^2 \equiv 1 \pmod p \iff a = \pm 1
ちょっと変形して
$ p-1 = 2^sdとしたとき、$ a^d \equiv 1 \pmod pまたは$ 0 \le ^\exists r \le s-1で$ a^{2^rd} \equiv -1 \pmod p
対偶を取って
$ a^d \not\equiv 1 \pmod pかつ$ 0 \le ^\forall r \le s-1で$ a^{2^rd} \not\equiv -1 \pmod pならば$ pは合成数
これをいろんな$ aで検証する。$ aをランダムに選んだときのハズレ率は$ 1/4らしい
計算量
入力$ n、検証回数$ kとして、$ O(k\log^3 n)らしい？
巨大な$ nに対して$ a^{2^rd}\bmod nの計算でオーバーフローしないように注意が必要
条件付きで決定的
$ nの上限がわかっているときは、$ aを適切に選ぶことで決定的アルゴリズムにできる。
$ n (\le 2^{32}) \le 4759123141のとき、$ a = 2, 7, 61
$ n (\le 10^{18}) \le 2^{64} のとき、$ a = 2, 325, 9375, 28178, 450775, 9780504, 1795265022
この$ aを使うときの実装上の注意
$ a \ge nのときは$ a \leftarrow a \bmod nとして検証する。
それで$ a = 0となったときは、$ nは素数。
参考