Miller Rabbin

個人的メモ

$n$ を奇素数とし, $n = 2^s d + 1$ ($s \ge 1$, $d$ は奇数) の形で表されているとき, $\forall a \in (\mathbb{Z} / n \mathbb{Z})^{\ast}$ について (I) $a^d = 1 (\mathrm{mod}\ n)$, (II) $\exists r (0 \le r < s), a^{2^r d} = -1 (\mathrm{mod}\ n)$ のいずれかが成り立つ(フェルマーの小定理を考えると分かる).
この対偶, つまり (I') $a^d$ が $n$ を法として $1$ に等しくなく, (II') $\forall r (0 \le r < s)$ について $a^{2^r d}$ が $n$ を法として $-1$ に等しくない場合は必ず $n$ は合成数となることがいえる.
よって適当に $\forall a \in (\mathbb{Z} / n \mathbb{Z})^{\ast}$ を何回か取ってきて (I'), (II') の $2$ つの性質を満たすかどうかを確かめることで $n$ が素数である場合なら必ず Yes, 合成数である場合は高い確率で No を返すようなアルゴリズムを考えることができる. なぜ高確率なのかとかいう評価は知らない.
ここで適当に選ぶ $\forall a \in (\mathbb{Z} / n \mathbb{Z})^{\ast}$ の集合として以下の実装コードにある numset を取ってくると必ず, 正しく素数であるかどうかを判定できることが実験的に知られている.