素数判定法

素数判定について、よく知られて、正しい方向性としては、Miller-Rabin 判定法と Solovay-Strassenの判定法があります。

[

l]Solovay Strassen の判定法 $n$ が与えられたとする。 $n$ と互いに素な $a$ に対して、

$$a^{(n-1)/2} \equiv \left( \frac{a}{n}\right) ($$Jacobi 記号$$) \mod n$$

が成り立てば、$a$ についてのテストは合格。

ランダムな $a$ ついて上記のようなテストを行い、不合格なら $n$ は素数ではなく、 合格なら $n$ が素数である可能性が上がる。 (テストを行うごとに誤判定の可能性を $1/2$ にできます。)

Jacobi 記号の知識/計算が必要なところが大変そうですが、 次の Miller-Rabin 判定法ではそれが必要なくなります。

[

l]Miller-Rabin判定法 $n$ が与えられたとする。$n-1$ を $2$ で割れるだけ割って、

$$n-1=2^s d \qquad(\gcd(d,2)=1)$$

と書く。このとき、

1. $a^d=1$ か
2. $a^{2^r d} =-1 \qquad(\exists(r\in \{0,\dots,s-1\})$

が成り立てば、$a$ についてのテストは合格。

ランダムな $a$ ついて上記のようなテストを行い、不合格なら $n$ は素数ではなく、 合格なら $n$ が素数である可能性が上がる。 (テストを行うごとに誤判定の可能性を $1/4$ にできます。)

詳しくは wikipedia にもあるのでそちらをご参照ください。