目次

  1. Msieve とは
  2. Msieve のインストール
    1. 安定版の Win32 用バイナリを利用する場合
    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.52、開発版が 1.53 です。安定版は Win32 用のバイナリとソースコードがアーカイブの形で配布されています。開発版は SVN でダウンロードします。

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

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

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

GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。

Msieve download | SourceForge.net からソースコードのアーカイブ msieve152.tar.gz をダウンロードして展開します。

~> tar zxf msieve152.tar.gz

展開されたディレクトリに移動します。

~> cd msieve-1.52
~/msieve-1.52> 

Makefile の 22~23 行目にある OPT_FLAGS を修正します。

OPT_FLAGS = -O3 -fomit-frame-pointer -march=core2 \
            -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE

-marchnative にします。また、Cygwin の環境では -lecm で失敗するので -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.52> 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. -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM -c -o common/filter/clique.o common/filter/clique.c
─── 中略 ───
demo.c:558:2: 警告: 配列の添字が ‘char’ 型です [-Wchar-subscripts]
  if (isdigit(buf[0]) || buf[0] == '(' ) {
  ^

~/msieve-1.52> 

できた実行ファイル msieve または msieve.exe をカレントディレクトリまたはパスの通っているディレクトリにコピーして使います。

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

GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。

開発版のためのディレクトリを掘ります。ここでは ~/msieve-svn とします。

~> mkdir ~/msieve-svn

開発版のためのディレクトリに移動します。

~> cd ~/msieve-svn
~/msieve-svn> 

SVN で開発版をダウンロードします。2 回目以降は同じ手順で更新されたファイルだけがダウンロードされます。このとき更新すべきファイルが書き換えられていると競合をどう処理するか訊いてくるので、their side of conflict を選択して最新版に更新してから後で編集し直します。

~/msieve-svn> svn checkout svn://svn.code.sf.net/p/msieve/code/trunk msieve-code
U    msieve-code/include/msieve.h
D    msieve-code/build.cuda.vc12/sort_engine_sm13
D    msieve-code/build.cuda.vc12/stage1_core_sm11
─── 中略 ───
U    msieve-code/demo.c
U    msieve-code/Changes
C    msieve-code/Makefile
リビジョン 988 をチェックアウトしました。
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> 

ソースコードのディレクトリに移動します。

~/msieve-svn> cd msieve-code
~/msieve-svn/msieve-code> 

Makefile の 22~23 行目にある OPT_FLAGS を修正します。

OPT_FLAGS = -O3 -fomit-frame-pointer -march=native \
            -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE

Cygwin の環境では -lecm で失敗するので -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="\"988M\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -DHAVE_GMP_ECM -c -o aprcl/mpz_aprcl32.o aprcl/mpz_aprcl32.c
─── 中略 ───
demo.c:564:2: 警告: 配列の添字が ‘char’ 型です [-Wchar-subscripts]
  if (isdigit(buf[0]) || buf[0] == '(' ) {
  ^

~/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 分 20 秒で分解できました。

~/msieve-svn/msieve-code> ./msieve -e -p -q -v "10^77+3"


Msieve v. 1.53 (SVN 988M)
Thu Jul 30 15:24:23 2015
random seeds: cd66920b 31011e49
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)
36727 relations (18730 full + 17997 combined from 196395 partial), need 36410
36727 relations (18730 full + 17997 combined from 196395 partial), need 36410
sieving complete, commencing postprocessing
begin with 215125 relations
reduce to 52460 relations in 2 passes
attempting to read 52460 relations
recovered 52460 relations
recovered 43534 polynomials
attempting to build 36727 cycles
found 36727 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 18730
   length 2 : 17997
largest cycle: 2 relations
matrix is 36314 x 36727 (5.3 MB) with weight 1090244 (29.69/col)
sparse part has weight 1090244 (29.69/col)
filtering completed in 3 passes
matrix is 26157 x 26220 (4.1 MB) with weight 859698 (32.79/col)
sparse part has weight 859698 (32.79/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 26109 x 26220 (2.5 MB) with weight 598996 (22.85/col)
sparse part has weight 402426 (15.35/col)
commencing Lanczos iteration
memory use: 2.6 MB
lanczos halted after 414 iterations (dim = 26107)
recovered 17 nontrivial dependencies
p39 factor: 185554311496620532371770351611143673123
p39 factor: 538925768921415130739706333069119686561
elapsed time 00:02:20

~/msieve-svn/msieve-code>