onewanのメモ帳

数式が書きたくて始めたブログ。twitter IDは @onewan

ミラー・ラビン素数判定法

素数判定のアルゴリズムとして高速なミラー・ラビン素数判定法をPythonで実行してみた。 実行環境は、最近Deep Learningでお世話になっているColaboratory*1を利用してみた。

驚きの速さでした。

これは、Colaboratoryの動作環境に寄るものも大きいと思いますが、664桁で数秒とか速すぎない?

素数 桁数 おおよその計算時間
21279 -1*2 386桁 1秒
22203 -1*3 664桁 4秒

コード

えいやで書いたので汚いですが、こんなコードです。
f:id:sosuu-daifugoh:20180624025030p:plain

参考文献

コードを書くのに以下のページを参考にしました。
ミラー–ラビン素数判定法 - Wikipedia qiita.com

*1:Googleが提供しているクラウドサービス。

*2:15番目のメルセンヌ素数

*3:16番目のメルセンヌ素数