ミラー＝ラビン素数判定法
確率的素数判定法だが、誤判定確率を任意に小さくできる
誤判定確率を小さくするには速度を犠牲にする
速度の犠牲が線形なのに対して、誤判定確率は指数関数的に小さくできるので効率は良い
準備
$ p^nを$ \hat pで表すことにする。
特に$ \hat2は$ \hat2=4や$ \hat2=1024など複数の値を取りうる変数である事に注意。
考え方
$ (\Z/p\Z)^\times\ (p\in\mathbb P_{\ge3})の単位元の平方根について考える。 $ 1\overset p\equiv1^2
$ 1\overset p\equiv(-1)^2
コレは自明。
$ 1\overset8\equiv3^2
$ 1\overset8\equiv5^2
$ 1\overset{12}\equiv5^2
$ 1\overset{15}\equiv4^2
$ (\Z/4\Z)^\times=\lang1,3\rang=\lang1,-1\rang
$ (\Z/6\Z)^\times=\lang1,5\rang=\lang1,-1\rang
$ (\Z/9\Z)^\times=\lang1,2,4,8,7,5\rang
$ =\lang1,2,4,-1,-2,-4\rang
$ x\overset p\equiv 1とする
$ x^2-1\overset p\equiv0
$ (x-1)(x+1)\overset p\equiv0
これが成立するのは$ x-1か$ x+1が$ pの約数である場合 ここで、奇素数$ p\in\mathbb P_{\ge3}について考える $ p-1=\hat{\bm2}d\quad(d\in{\rm Odd})となる
すると任意の$ a\in(\Z/p\Z)^\timesにおいて以下が成立する
$ a^d\overset p\equiv1
または$ a^{\hat 2d}\overset p\equiv-1\quad(\exist \hat 2\le\hat{\bm2}/2)
証明
$ a^{p-1}\overset p\equiv1
$ a^{p-1}=a^{\hat{\bm2}d}\overset p\equiv1
$ a^{\hat{\bm2}d}の平方根は$ -1か$ 1 $ a^{\hat 2d}=a^{\hat{\bm2}d/2}\quad(\hat2=\hat{\bm2}/2)とする
-1 の場合
$ a^{\hat2d}\overset p\equiv-1
1 の場合
$ a^{\hat2d}\overset p\equiv1
どこかで -1 として引っかかれば、以下が成立
$ a^{\hat2d}\overset p\equiv-1\qquad(\exist\hat2\le\hat{\bm2}/2)
最後まで 1 だった場合
$ a^d\overset p\equiv1
すべての場合分けをまとめると、任意の$ a\in(\Z/p\Z)^\timesにおいて
$ a^d\overset p\equiv1
または$ a^{\hat2d}\overset p\equiv-1\quad(\exist\hat2\le\hat{\bm2}/2)
ある$ a\in(\Z/n\Z)^\timesにおいて以下の式が成立したら奇数$ n\in{\rm Odd}は合成数 $ \begin{cases}a^d\overset n{\not\equiv}1\\a^{\hat2d}\overset n{\equiv}1\quad(\forall\hat2\le\hat{\bm2}/2)\end{cases}
このとき、$ aは$ nが合成数である証人となる
奇数の合成数$ nに対しては殆ど全ての$ aが証拠となるある。 上手く証人$ aを当てる方法は知られていないのでランダムにアタックする
殆どの$ aが証人なので高い確率で$ nが合成数であると検出できる 入力: $ n\in{\rm Odd}\quad(n\ge3),$ k\in\N: 判定の正確度を表すパラメータ
出力: $ nが合成数ならcomposite, さもなくば probably prime 動作
1. $ n-1=\hat{\bm2}dを満たす$ dを見つける
2. 以下を$ k回繰り返す
1. $ a\in[1, n-1]\subset\N を乱択する
2.$ a^d\overset n{\equiv}1なら$ kを更新してやり直す (continue)
3. $ a^{\hat 2d}\overset n{\not\equiv}-1\quad(\forall \hat2\le\hat{\bm2}/2)なら composite を返す
3. probably prime を返す
評価
平方の繰り返しを冪乗余を使って実現すると、実行時間は$ \Omicron(k\log^3n)となる 乗算を FFT ベースのものにすると$ \tilde\Omicron(k\log^2n)になる 強い嘘つきの$ aを引く確率を$ \varepsilonとすると、毎回独立な$ aを取ってくるなら正解率は$ 1-\varepsilon^kになる。 $ \varepsilon<\frac14らしい。
任意の奇数の合成数$ nについて、$ aの少なくとも 3/4 が合成性の証拠となることがわかっている。
実際の誤判定確率は平均的には$ 4^{-k}よりはずっと小さい 暗号に利用する場合は最悪のケースを考えて$ 4^{-k}のみを信じるべきとのこと
$ aとして素数を小さい順に選んでいくと効率よく判定できる