GolangでMiller-Rabin素数判定法を実装してみる - 逆さまにした背景 Wikipedia にも記載されていますが、 Miller-Rabin素数判定法は 与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。 フェルマーテストでは、以下のフェルマーの小定理を用いて 素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。 例えば、最小のカーマイケル数は561ですが、のため、素数ではありません。 フェルマーの小定理 素数 と互いに素となる整数 に対して が成り立つ。 フェルマーテストを改良したのがMiller-Rabin素数判定法です。 詳細はWikipediaを参照頂ければと思いますが、与えられた素数を奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、 と表現します。ここで は正整数で、 は奇数です。すると式(1)は以下のように書けます。
