0. 素因数分解
素早く素因数分解をする一番有名な方法として$1 \le i \le \sqrt{N}$まで試し割してみることが知られています。
ですがこの手法は計算量が$O(\sqrt{N})$で制約が比較的小さい競技プログラミングでは有効ですがそれ以外の場面では時間がかかりすぎてしまいます。
そこで今回はMsieveという外部ツールを用いて素因数分解をやってみたいと思います。
Msieveは有名な高速な素因数分解の手法である楕円曲線法（ECM）、複数多項式二次ふるい法（MPQS）、一般数体ふるい法（GNFS)が高速に実行できる便利なツールです
1. 環境
- Windows10
- Windows Subsystem for Linux 2(WSL2)
まだWLS2を導入してないのであれば以下のサイトが参考になると思います。
Windows 10でLinuxを使う(WSL2)
2. Msieveのインストール
以下のサイトに飛んでDownloadをクリックしてください
Msieveをダウンロード
Linux上でソースコードをコンパイルして実行するので以下のコマンドを順次実行します
まずはパッケージをダウンロード
$ sudo apt-get install build-essential libgmp3-dev zlib1g-dev libecm-dev
以下のコマンドでコンパイルができる
$ wget "http://downloads.sourceforge.net/project/msieve/msieve/Msieve%20v1.52/msieve152.tar.gz?r=&ts=1452107977&use_mirror=jaist" -O msieve152.tar.gz
$ tar xvf msieve152.tar.gz
$ cd msieve-1.52/
$ make all ECM=1
コンパイルが終了したら以下のコマンドでMsieveの実行オプションを見ることができる
$ ./msieve --help
後でよく使うオプションをあげておく
#3. Msieveを実行してみる
./msieve オプション 正整数
さきほどのコマンドが全部実行できたならば上のコマンドで素因数分解を行うことができる。
よく使うであろうオプション
-v :ログを画面に出力
-e :15桁を超える素因数を探す
-q :ログファイルに出力しない
基本的にこの3つぶちこんとけばOKである
以下は実行例
$ ./msieve -e -v -q 831416828080417866340504968188990032810316193533653516022175784399720141076262857
831416828080417866340504968188990032810316193533653516022175784399720141076262857
prp40: 1593021310640923782355996681284584012117
prp42: 521911930824021492581321351826927897005221
私の環境だとこれの実行に4分かかったのでみなさんも根気強く実行が終わるのを待ちましょう。ちなみにサマーウォーズでおなじみのRSA暗号は桁数によっちゃこれで簡単に突破することができます。RSA暗号についての詳しい説明は準備中なので次回にご期待ください！