Msieve は MPQS 法 (the self-initializing Multiple Polynomial Quadratic Sieve; 自己初期化複数多項式二次ふるい法) と GNFS 法 (the General Number Field Sieve; 一般数体ふるい法) を用いる素因数分解プログラムです。前処理として P-1 法、P+1 法、ECM (Elliptic Curve Method; 楕円曲線法) なども実装しており、さまざまな数に柔軟に対応します。作者は Jason Papadopoulos さんです。
これを書いている時点で Msieve のバージョンは安定版が 1.53、開発版が 1.54 です。安定版は Win64 用のバイナリとソースコードがアーカイブの形で配布されています。開発版は SVN でダウンロードします。
Msieve download | SourceForge.net から msieve153_win64.zip をダウンロードして msieve153.exe を取り出します。
補足 : Norton Internet Security を利用していると WS.Reputation.1 を理由に msieve153.exe が削除されてしまいます。ウイルスが検出されたわけではなく、暗号化技術と関わりがある素因数分解を行うこと自体が脅威と判断されているようです。「復元してこのファイルを除外する」で復元できます。
GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。
Msieve download | SourceForge.net からソースコードのアーカイブ msieve153_src.tar.gz をダウンロードして展開します。
~> tar zxf msieve153_src.tar.gz
展開されたディレクトリに移動します。
~> cd msieve-1.53 ~/msieve-1.53>
Cygwin の環境では -lecm で失敗するので Makefile の 23～24 行目にある OPT_FLAGS に -L/usr/local/lib を追加します。
OPT_FLAGS = -O3 -fomit-frame-pointer -march=native \ -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib
make します。
~/msieve-1.53> make all ECM=1
gcc -O3 -fomit-frame-pointer -march=native -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib -Wall -W -DMSIEVE_SVN_VERSION="\"Unversioned directory\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM -c -o aprcl/mpz_aprcl32.o aprcl/mpz_aprcl32.c
─── 中略 ───
gcc -O3 -fomit-frame-pointer -march=native -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib -Wall -W -DMSIEVE_SVN_VERSION="\"Unversioned directory\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM demo.c -o msieve \
libmsieve.a -lecm -ldl -lz -lgmp -lm -lpthread
~/msieve-1.53> できた実行ファイル msieve または msieve.exe をカレントディレクトリまたはパスの通っているディレクトリにコピーして使います。
GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。
開発版のためのディレクトリを掘ります。ここでは ~/msieve-svn とします。
~> mkdir ~/msieve-svn
開発版のためのディレクトリに移動します。
~> cd ~/msieve-svn ~/msieve-svn>
SVN で開発版をダウンロードします。2 回目以降は同じ手順で更新されたファイルだけがダウンロードされます。
~/msieve-svn> svn checkout svn://svn.code.sf.net/p/msieve/code/trunk msieve-code
D msieve-code/b40c
U msieve-code/Changes
G msieve-code/Makefile
─── 中略 ───
A msieve-code/cub/cub/warp/warp_reduce.cuh
A msieve-code/cub/cub/warp/warp_scan.cuh
A msieve-code/cub/sort_engine.h
リビジョン 1009 をチェックアウトしました。
~/msieve-svn> 更新すべきファイルが書き換えられているときは競合をどう処理するか訊いてくるので、their side of conflict を選択して最新版に更新してから後で編集し直します。
Conflict discovered in file 'msieve-code/Makefile'.
Select: (p) postpone, (df) show diff, (e) edit file, (m) merge,
(mc) my side of conflict, (tc) their side of conflict,
(s) show all options: tc
'msieve-code/Makefile' の競合状態を解消しましたソースコードのディレクトリに移動します。
~/msieve-svn> cd msieve-code ~/msieve-svn/msieve-code>
Cygwin の環境では -lecm で失敗するので Makefile の 23～24 行目にある OPT_FLAGS に -L/usr/local/lib を追加します。
OPT_FLAGS = -O3 -fomit-frame-pointer -march=native \ -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib
make します。
~/msieve-svn/msieve-code> make all ECM=1
gcc -O3 -fomit-frame-pointer -march=native -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib -Wall -W -DMSIEVE_SVN_VERSION="\"1009M\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM -c -o aprcl/mpz_aprcl32.o aprcl/mpz_aprcl32.c
─── 中略 ───
gcc -O3 -fomit-frame-pointer -march=native -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -L/usr/local/lib -Wall -W -DMSIEVE_SVN_VERSION="\"1009M\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM demo.c -o msieve \
libmsieve.a -lecm -ldl -lz -lgmp -lm -lpthread
~/msieve-svn/msieve-code> できた実行ファイル msieve または msieve.exe をカレントディレクトリまたはパスの通っているディレクトリにコピーして使います。
メモ : CUDA の開発環境が利用できる場合は make のオプションに CUDA=1 を追加すると GPU も活用するそうです。
Msieve は分解したい数 (を表す式) をコマンドラインに書くだけでその数を素因数分解してくれます。式を書くときは "～" で囲みましょう。
~/msieve-svn/msieve-code> ./msieve オプション "分解したい数を表す式"
-h または -? | 使用法を表示します。 |
-s < 中間ファイル名 > | 中間ファイル名を msieve.dat から変更します。 |
-l < ログファイル名 > | ログファイル名を msieve.log から変更します。 |
-i < 入力ファイル名 > | 分解したい数をファイルから入力します。 |
-m | 分解したい数を標準入力から入力します。 |
-q | ログファイルに出力しません。 |
-d < デッドライン (分)> | 篩が時間内に終わらないとき分解を中止します。 |
-r <relation の数の上限 > | relation の数が上限を超えたとき分解を中止します。 |
-p | 優先度を下げて実行します。 |
-v | ログを画面に出力します。 |
-g < 使用する GPU の数 > | GPU を使います。 0 ≤ 使用する GPU の数 < グラフィックカードの枚数 CUDA=1 で make したときだけ指定できます。 |
-t < スレッドの数の上限 > | スレッド数の上限を指定します。 |
| ECM のオプション | |
|---|---|
-e | 15 桁 を超える素因数を ECM で探します。 |
| MPQS 法のオプション | |
-c | MPQS 法のとき篩だけ行います。 |
| GNFS 法のオプション | |
-n | 80 桁を超える合成数を GNFS 法で分解します。 |
-nf <factor base ファイル名 > | factor base ファイル名を msieve.fb から変更します。 |
-np | NFS の多項式の選択だけ行います。 |
-np1 | NFS の多項式の選択のステージ 1 だけ行います。 |
-nps | NFS の多項式のサイズの最適化を行います。 |
-npr | NFS の多項式のルートの最適化を行います。 |
-ns | NFS の篩だけ行います。 |
-nc | NFS の combining だけ行います。 |
-nc1 | NFS の filtering だけ行います。 |
-nc2 | NFS の linear algebra だけ行います。 |
-ncr | NFS の linear algebra を前回のチェックポイントから再開します。 |
-nc3 | NFS の square root だけ行います。 |
GNFS 法のオプションには多数のサブオプションがあります。-h で表示される使用法を参照してください。
Ctrl-C で分解を中断できます。中間ファイル msieve.dat が残っているとき直前に中断した分解を途中から再開できます。
オプションを指定しなければ結果はログファイル msieve.log に追記されます。
78 桁の数 1077+3 が 2 分 37 秒で分解できました。
~/msieve-svn/msieve-code> ./msieve -e -p -q -v "10^77+3" Msieve v. 1.54 (SVN 1009M) Mon Apr 3 05:19:19 2017 random seeds: 1cafb0ef ef395b63 factoring 100000000000000000000000000000000000000000000000000000000000000000000000000003 (78 digits) searching for 15-digit factors searching for 20-digit factors commencing quadratic sieve (78-digit input) using multiplier of 7 using generic 32kb sieve core sieve interval: 12 blocks of size 32768 processing polynomials in batches of 17 using a sieve bound of 924083 (36314 primes) using large prime bound of 92408300 (26 bits) using trial factoring cutoff of 26 bits polynomial 'A' values have 10 factors sieving in progress (press Ctrl-C to pause) 36778 relations (18674 full + 18104 combined from 196956 partial), need 36410 36778 relations (18674 full + 18104 combined from 196956 partial), need 36410 sieving complete, commencing postprocessing begin with 215630 relations reduce to 52642 relations in 2 passes attempting to read 52642 relations recovered 52642 relations recovered 43638 polynomials attempting to build 36778 cycles found 36778 cycles in 1 passes distribution of cycle lengths: length 1 : 18674 length 2 : 18104 largest cycle: 2 relations matrix is 36314 x 36778 (5.3 MB) with weight 1093347 (29.73/col) sparse part has weight 1093347 (29.73/col) filtering completed in 3 passes matrix is 26402 x 26466 (4.1 MB) with weight 867118 (32.76/col) sparse part has weight 867118 (32.76/col) saving the first 48 matrix rows for later matrix includes 64 packed rows matrix is 26354 x 26466 (2.6 MB) with weight 602217 (22.75/col) sparse part has weight 406108 (15.34/col) commencing Lanczos iteration memory use: 2.6 MB lanczos halted after 418 iterations (dim = 26353) recovered 17 nontrivial dependencies p39 factor: 185554311496620532371770351611143673123 p39 factor: 538925768921415130739706333069119686561 elapsed time 00:02:37 ~/msieve-svn/msieve-code>