超高速な素因数分解をしてみたい…
そんな時、有能なツールの噂を効きました。
その名も msieve というライブラリです。
- 複数の高速アルゴリズムを使い、
- 巨大素数でも爆速で素因数分解可能
- Linux/Windows両方に対応してる
とても興味があったので使ってみました。
でもLinuxでのインストールに苦戦したので、
参考にCentOSでのビルド手順を残しておきます。
このページの目次
０．msieveの概要、高速に素因数分解できる理由
これはC言語で実装されたライブラリです。
▼ 概要としてはこんな感じ
Msieve is a C library implementing a suite of algorithms to factor large integers. It contains an implementation of the SIQS and GNFS algorithms; the latter has helped complete some of the largest public factorizations known
▼ 上記の意訳
Msieveは巨大整数を因数分解するアルゴリズム群を実装したCライブラリです。SIQSとGNFSっていうアルゴリズム実装が含まれていて、後者は知られている巨大数の素因数分解にも貢献している。
なんかすごそうなライブラリ。
自前で素因数分解するよりも遥かに高効率です。
参考 ： JavaScriptで超高速な素因数分解！osa_k法の実装例／欠点
早速CentOSにインストールしてみました。
※ これが大変だった…
１．GMPをビルド＆インストール
初めにGMPをインストールします。
これは多倍長演算をおこなえるライブラリ。
これがMsieveビルドに必要になってきます。
▼ ターミナルで以下を実行していく
|
1 2 3 4 5 6 7 |
$ wget https://gmplib.org/download/gmp/gmp-6.1.2.tar.xz $ tar -xvf gmp-6.1.2.tar.xz $ cd gmp-6.1.2/ $ ./cofigure $ make all $ make install |
これでGMPのインストールは完了
もし"No usable m4 "エラーが出たなら…
僕の環境(CentOS)では、以下エラーが出ました。
▼ なんかエラーが出てきた
|
1 |
checking for suitable m4... configure: error: No usable m4 in $PATH or /usr/5bin (see config.log for reasons). |
この解決に苦戦してしまった。
ただググると解決策が出てきました。
▼ Ubuntuにgcc、GMPをインストールする
この手順でGMPインストール成功です。
２．Msieveをビルド＆インストール
いよいよMsieveをインストールしてみます。
以下の手順を実行するだけです。
|
1 2 3 4 5 6 7 8 9 10 11 |
## CentOS環境なら以下 $ sudo yum install -y build-essential libgmp3-dev zlib-dev libecm-dev ## UbuntuOS環境なら以下 $ sudo apt install -y build-essential libgmp3-dev zlib1g-dev libecm-dev ## ビルドとインストール実行 $ wget https://jaist.dl.sourceforge.net/project/msieve/msieve/Msieve%20v1.53/msieve153_src.tar.gz $ tar xvf msieve153_src.tar.gz $ cd msieve-1.53 $ make all |
これでmsieveがビルドされました。
ググるとビルド時に make all ECM=1 としている記事が多いですが、環境によってはEMCが使えないためECMなしでビルドしてます（CentOSではEMCがインストールできなかった）
あと先ほど書いたようにGMPなど他ライブラリに依存するので、ないならビルド・インストしてください。僕自身もそれでちょっと苦戦しました。
ひとまず実行環境が準備できたのでヨシ
３．msieveで巨大数を素因数分解
ということで素因数分解やってみます。
▼ 色々な数を素因数分解してみた
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
$ ./msieve -q -v 2023 factoring 2023 (4 digits) p1 factor: 7 p2 factor: 17 p2 factor: 17 elapsed time 00:00:00 $ ./msieve -q -v 273335211246073180767438793192212499213 factoring 273335211246073180767438793192212499213 (39 digits) prp39 factor: 273335211246073180767438793192212499213 elapsed time 00:00:00 $ ./msieve -q -v 123456789012345678901234567890123456789012345678901234567890123456789 factoring 123456789012345678901234567890123456789012345678901234567890123456789 (69 digits) ... p1 factor: 3 p1 factor: 3 p2 factor: 71 p3 factor: 239 p4 factor: 3607 p4 factor: 3803 p4 factor: 4649 p6 factor: 123551 p6 factor: 909091 p7 factor: 4147571 prp18 factor: 102598800232111471 prp18 factor: 265212793249617641 elapsed time 00:00:01 |
う～～ん、本当に爆速でビックリ
上記のように30桁とか70桁の素因数分解でもほぼ一瞬でおこなってくれます。実行結果を p3: 239 , p6: 909091 みたいに桁数付きで教えてくれるのも便利です。
使ってみて少しだけ感動を覚えました。
メモリ1GBの環境でも爆速で動いた
そして環境的な制約もありません。
現に以下環境でも問題なく動作しました。
- OS : Amazon Linux 2
- EC2タイプ : t2.micro
- メモリ : 1GB
- コア数 : 1個
- ストレージ : 8GB
これはEC2最低レベルのインスタンスです。
それでもmsieveが優秀であるためか、こんなメモリ容量でも爆速で動かせました。70桁程度の素因数分解なら一瞬です。
ただ70桁を超えると数秒ほどかかるケースが増え、80桁以上では実用的な実行速度であるかは不明です。実用的な範囲では70～80桁が限界ですね。
でもメチャクチャ優秀だと思う。
