GolangでMiller-Rabin素数判定法を実装してみる

背景

Wikipedia にも記載されていますが、 Miller-Rabin素数判定法は 与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。
フェルマーテストでは、以下のフェルマーの小定理を用いて 素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。 例えば、最小のカーマイケル数は561ですが、 561 = 3 \times 11 \times 17のため、素数ではありません。

フェルマーの小定理
p:素数
a:pと互いに素となる整数
に対して
a^{p-1} \equiv 1 \ mod \ p \tag{1}
が成り立つ。

フェルマーテストを改良したのがMiller-Rabin素数判定法です。 詳細はWikipediaを参照頂ければと思いますが、与えられた素数 pを奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、 p-1 = 2^{s} \cdot d と表現します。ここで s は正整数で、 d は奇数です。すると式(1)は以下のように書けます。

a^{2^{s}d} \equiv 1 \ mod \ p \tag{2}

pが素数であれば、式(2)を満たします。左辺を \bigl( a^{d \cdot 2^{s-1}} \bigr)^{2}とみて、式(2)について単位元の平方根を考えます。
非自明な平方根は存在しない(証明もWikipediaにあります)ので以下の2式のみを考えればよいことになります。

a^{d} \equiv 1 \ mod \ p \tag{3}

a^{2^{r}d} \equiv -1 \ mod \ p \tag{4}

ここで、 0 \leq r \leq s - 1です。 上記は、自明な平方根 1または -1となった場合を考えて、 1となった場合は、さらに繰り返し(平方根が -1となるまで)平方根を考えていった結果を表しています。式(3)は -1にならず、平方根が取れなくなるまで取ったあとの結果になります。
あとはフェルマーテストと同様に考えて、与えられた数が素数でない(合成数である)のであれば、式(3)および式(4)を満たさないとして、素数判定を行います。 フェルマーテストと同様に偽陽性(素数と判定したのに実は合成数だった)の可能性は残りますが、フェルマーテストより確率は低いようです。

実装

gist1cd38a67c96df7966b9c468927dc2757

結果

今回は以下の4パターンを判定してみました。

結果は以下の通り、いずれも正しく判定できています。

$ go run MillerRabinPrimalityTest.go
------------Prime-------------
2 :  true
3 :  true
5 :  true
7 :  true
11 :  true
13 :  true
17 :  true
19 :  true
23 :  true
29 :  true
31 :  true
37 :  true
41 :  true
43 :  true
47 :  true
53 :  true
59 :  true
61 :  true
67 :  true
71 :  true
73 :  true
79 :  true
83 :  true
89 :  true
97 :  true
------------Composite-------------
9 :  false
15 :  false
21 :  false
25 :  false
27 :  false
33 :  false
35 :  false
39 :  false
45 :  false
49 :  false
51 :  false
55 :  false
57 :  false
63 :  false
65 :  false
69 :  false
75 :  false
77 :  false
81 :  false
85 :  false
87 :  false
91 :  false
93 :  false
95 :  false
99 :  false
16329805957987392833 :  false
75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 :  true

今回は aをランダムに選ぶ回数kをk=20としましたが、精度を上げるにはこの値を増やすことが有効です。逆にk=1などとしてみると以下のように結構間違えます。もちろん乱択アルゴリズムなので何度もやるとミスがあったりなかったりですが。

$ go run MillerRabinPrimalityTest.go
------------Prime-------------
2 :  true
3 :  true
5 :  true
7 :  true
11 :  true
13 :  true
17 :  true
19 :  true
23 :  true
29 :  true
31 :  true
37 :  true
41 :  true
43 :  true
47 :  true
53 :  true
59 :  true
61 :  true
67 :  true
71 :  true
73 :  true
79 :  true
83 :  true
89 :  true
97 :  true
------------Composite-------------
9 :  false
15 :  false
21 :  false
25 :  false
27 :  true
33 :  false
35 :  false
39 :  true
45 :  false
49 :  false
51 :  false
55 :  false
57 :  false
63 :  false
65 :  false
69 :  false
75 :  false
77 :  false
81 :  false
85 :  false
87 :  false
91 :  true
93 :  false
95 :  false
99 :  false
16329805957987392833 :  false
75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 :  true

Reference