目次

  1. Msieve とは
  2. Msieve のインストール
    1. 安定版の Win64 用バイナリを利用する場合
    2. 安定版のソースコードを利用する場合
    3. 開発版を利用する場合
  3. Msieve の使い方
    1. 主なオプション
    2. 使用例

1. Msieve とは

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 さんです。

2. Msieve のインストール

これを書いている時点で Msieve のバージョンは安定版が 1.53、開発版が 1.54 です。安定版は Win64 用のバイナリとソースコードがアーカイブの形で配布されています。開発版は SVN でダウンロードします。

2.1. 安定版の Win64 用バイナリを利用する場合

Msieve download | SourceForge.net から msieve153_win64.zip をダウンロードして msieve153.exe を取り出します。

補足 : Norton Internet Security を利用していると WS.Reputation.1 を理由に msieve153.exe が削除されてしまいます。ウイルスが検出されたわけではなく、暗号化技術と関わりがある素因数分解を行うこと自体が脅威と判断されているようです。「復元してこのファイルを除外する」で復元できます。

2.2. 安定版のソースコードを利用する場合

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 をカレントディレクトリまたはパスの通っているディレクトリにコピーして使います。

2.3. 開発版を利用する場合

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 も活用するそうです。

3. Msieve の使い方

Msieve は分解したい数 (を表す式) をコマンドラインに書くだけでその数を素因数分解してくれます。式を書くときは "~" で囲みましょう。

~/msieve-svn/msieve-code> ./msieve オプション "分解したい数を表す式"

3.1. 主なオプション

Msieve の主なオプション (demo.c より)
-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 のオプション
-e15 桁 を超える素因数を ECM で探します。
MPQS 法のオプション
-cMPQS 法のとき篩だけ行います。
GNFS 法のオプション
-n80 桁を超える合成数を GNFS 法で分解します。
-nf <factor base ファイル名 >factor base ファイル名を msieve.fb から変更します。
-npNFS の多項式の選択だけ行います。
-np1NFS の多項式の選択のステージ 1 だけ行います。
-npsNFS の多項式のサイズの最適化を行います。
-nprNFS の多項式のルートの最適化を行います。
-nsNFS の篩だけ行います。
-ncNFS の combining だけ行います。
-nc1NFS の filtering だけ行います。
-nc2NFS の linear algebra だけ行います。
-ncrNFS の linear algebra を前回のチェックポイントから再開します。
-nc3NFS の square root だけ行います。

GNFS 法のオプションには多数のサブオプションがあります。-h で表示される使用法を参照してください。

Ctrl-C で分解を中断できます。中間ファイル msieve.dat が残っているとき直前に中断した分解を途中から再開できます。

オプションを指定しなければ結果はログファイル msieve.log に追記されます。

3.2. 使用例

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>