Miller-Rabinテスト
確率的な素数判定法
素数$ pを$ p-1=2^srと仮定する
ただし、$ rは奇数
$ sは適当に自分で設定するっぽい
その大きさに対する何かメリット的なものってあるんか #?? 小さいと計算が簡単になる。$ s=2とか
このとき任意の$ 1\le a\le p-1である$ aに対し、以下が成り立つ
$ a^r\equiv1\pmod p、または、$ a^{2^jr}\equiv-1\pmod p
となる整数$ j(0\le j\le s-1)が存在する
したいこと
$ nが素数かどうかを判定したい
$ nが素数ならこれは奇数なので、$ n-1は偶数で因数2を持つ
なので、この$ n-1を$ 2^srと表す
$ rは奇数。$ sは奇素数
$ rは$ n-1を繰り返し2で割った結果mrsekut.icon
ex. $ n=11のとき$ n-1=10=2^15
$ (x-1)(x+1)\equiv0\pmod nを考えたときに、
$ nが素数なら$ x=\pm1になる
逆に言えば、$ x=\pm1になるような$ nを探せば$ nは素数である
参考