確率的な素数判定法

素数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で割った結果

なんでこんなふうに表すの #??

ex. n=11のときn-1=10=2^15

これのミラーラビン法のアイディアのところのメモ

(x-1)(x+1)\equiv0\pmod nを考えたときに、

nが素数ならx=\pm1になる

逆に言えば、x=\pm1になるようなnを探せばnは素数である

違うかも、 #??

参考

『現代暗号の基礎数理』 8章