素数を高い確率で高速に判定するミラーラビン判定法

与えられた数が素数かどうかを高い確率で高速に判定するアルゴリズムとしてミラーラビン(Miller-Rabin)判定法があります。
暗号の実装で素数が必要な時にこの判定法が使われることが多いようです。
厳密に素数かどうかを判定する方法として、試行割算法(Trial Division)というものもありますが、
${10}^{6}$ を超える値に対しては、時間がかかりすぎてしまいます。ミラーラビン判定法の数学上の根拠となる定理を見ていきます。

<定理1>
nは奇素数であり a は n と互いに素な整数であるとする。
n-1の素因数2を全てべきに抜き出し、
$n-1 = {2} ^ {s} d$
の形とする。この時、以下のi),ii)のどちらかが成り立つ。
i) ${a} ^ {d} = 1 \mod n$
ii) ${a} ^ { {2} ^ {r} d } = -1 \mod n$ となるrが集合{0, 1, ..., s-1}に存在する。

参考:
ミラー–ラビン素数判定法 - Wikipedia

この定理を使って、ミラーラビン判定法を定義します。
<ミラーラビン判定法>
判定したい奇数をnとする。
aを{1, 2, 3, ..., n-1}からランダムに選び出す。
n-1の素因数2を全て抜き出し(奇数になるまで2で割り算する)、sとdを決定する。
${a} ^ {d} \mod n$ を計算し、1であれば、[おそらく素数]とする。
全てのr:{0, 1, 2, ..., s-1}に対して、
${a} ^ { {2} ^ {r} d } \mod n$ を計算し、-1であれば、[おそらく素数]とする。上記以外の場合[おそらく合成数]とする。

このロジックに厳密性はなく、あくまでも素数である確率の判定法であることに注意する。
この判定法の確度はどのくらいなのかを示したが次の定理である。

<定理2>
nが奇数の合成数であるにも関わらず、
ミラーラビン判定法が[おそらく素数]を返すaの個数は{1, 2, 3, ..., n-1}のうち、
約1/4である。

参考:
http://www.a-phys.eng.osaka-cu.ac.jp/suri-g/miller-rabin.pdf

定理2により、1回のミラーラビン判定の結果が、実際は合成数であるのに[おそらく素数]と判定される確率は約1/4です。
この定理を使うと、合成数nに対して異なる整数a0, a1がともに[おそらく素数]の判定を下す確率は約1/16となります。
つまり、異なるaに対してたくさん繰り返せば、誤判定をする確率を減らすことができるということです。

以下の論文によると、 kビットの数に対して、1回のミラーラビン判定が誤判定される確率は、
$p_k \leq {k} ^ {2} {4} ^ { 2 - \sqrt {k} }$
$(k \geq 2)$ なので、
k=256ビットに対しては ${2}^{-12}$
k=2048ビットに対しては ${2} ^ { -63 }$
k=4096ビットに対しては ${2} ^ { -100 }$ となります。