のだなのだ

ほげ〜

リュカレーマーテストとミラーラビンテスト

※リュカレーマーテストもミラーラビンテストもWiki見ればわかるので説明は省略します。

 少し前にリュカレーマーテストを使って下から順にメルセンヌ素数を探すプログラムを組んだのですが、7~8時間かかって28番目が出ないという感じでした。

 リュカレーマーテストは指数の二乗に比例して実行時間が伸びる気がするので、「リュカレーマーテストで全部の候補をテストするの効率悪すぎやろ」ってなって「これ確率的な方法である程度目星つけてからやってんのとちゃうか?」と思い、確率的素数判定アルゴリズムとして非常に有名なミラーラビンテストを実装して試しにサクッと組んで実装してみました。

 

2の9941乗-1を判定した(擬素数対策に100回判定)(乱数は64bit)

f:id:coilgunrailgun:20161028051804p:plain

ちなみにリュカレーマー

f:id:coilgunrailgun:20161028052213p:plain

ミラーラビンで一回しか判定しなくても0.4秒かかるのでリュカレーマーテストの方が速い

 

 やはり任意の数を判定できるアルゴリズムなのでメルセンヌ素数に特化したアルゴリズムにはかなわないようです。

 それにしても離散演算するとは言えGIMPSはどうやって49番目とか見つけたんでしょうね