ミラー・ラビン素数判定法
素数判定のアルゴリズムとして高速なミラー・ラビン素数判定法をPythonで実行してみた。
実行環境は、最近Deep Learningでお世話になっているColaboratory*1を利用してみた。
驚きの速さでした。
これは、Colaboratoryの動作環境に寄るものも大きいと思いますが、664桁で数秒とか速すぎない?
素数 | 桁数 | おおよその計算時間 |
---|---|---|
21279 -1*2 | 386桁 | 1秒 |
22203 -1*3 | 664桁 | 4秒 |
コード
えいやで書いたので汚いですが、こんなコードです。
参考文献
コードを書くのに以下のページを参考にしました。
ミラー–ラビン素数判定法 - Wikipedia
qiita.com