Msieve の使い方
目次
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 さん です。Msieve | Download Msieve software for free at SourceForge.net で入手できます。
2. Msieve のインストール
これを書いている時点で Msieve のバージョンは安定版が 1.47、開発版が 1.48 です。安定版はソースコードと Win32 用のバイナリの形で配布されています。開発版は SVN でダウンロードします。
Win32 用バイナリを利用する場合
Msieve | Get Msieve at SourceForge.net から msieve147.zip をダウンロードして msieve.exe を取り出します。
安定版を利用する場合
GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。
Msieve | Get Msieve at SourceForge.net からソースコードのアーカイブ msieve147.tar.gz をダウンロードして展開します。
~> tar zxf msieve147.tar.gz ~> cd msieve-1.47 ~/msieve-1.47>
必要ならば Makefile を修正します。
make します。Intel/AMD の 32 ビット環境は make x86 ECM=1、64 ビット環境は make x86_64 ECM=1、その他は make generic ECM=1 です。
~/msieve-1.47> make x86 ECM=1 (Intel/AMD の 32 ビット環境のとき) または make x86_64 ECM=1 (Intel/AMD の 64 ビット環境のとき)
できた実行ファイル msieve または msieve.exe をカレントディレクトリかパスの通っているディレクトリにコピーして使います。
開発版を利用する場合
GMP-ECM の使い方 を参照して Cygwin と GMP と GMP-ECM をインストールしておきます。
開発版のためのディレクトリを掘ります。ここでは ~/msieve-svn とします。
~> mkdir ~/msieve-svn
開発版のためのディレクトリに移動します。
~> cd ~/msieve-svn
~/msieve-svn>
SVN で開発版をダウンロードします。2 回目以降は同じ手順で更新されたファイルだけがダウンロードされます。
~/msieve-svn> svn co https://msieve.svn.sourceforge.net/svnroot/msieve msieve
ソースコードのディレクトリに移動します。
~/msieve-svn> cd msieve/trunk
~/msieve-svn/msieve/trunk>
必要ならば Makefile を修正します。
make します。Intel/AMD の 32 ビット環境は make x86 ECM=1、64 ビット環境は make x86_64 ECM=1、その他は make generic ECM=1 です。
~/msieve-1.47> make x86 ECM=1 (Intel/AMD の 32 ビット環境のとき) または make x86_64 ECM=1 (Intel/AMD の 64 ビット環境のとき)
できた実行ファイル msieve または msieve.exe をカレントディレクトリかパスの通っているディレクトリにコピーして使います。
メモ: CUDA の開発環境が利用できる場合は make のオプションに CUDA=1 を追加すると GPU も活用するそうです。
3. Msieve の使い方
Msieve は分解したい数 (を表す式) をコマンドラインに書くだけでその数を素因数分解してくれます。式を書くときは "～" で囲みましょう。
~/msieve-1.47> ./msieve オプション "分解したい数を表す式"
オプション一覧
以下のコマンドラインオプションがあります。
| -s <中間ファイル名> | 中間ファイル名を msieve.dat から変更します。 |
| -l <ログファイル名> | ログファイル名を msieve.log から変更します。 |
| -i <入力ファイル名> | 分解したい数をファイルから入力します。 |
| -m | 分解したい数を標準入力から入力します。 |
| -mb <メモリのサイズ (MB)> | 後処理に使用するメモリのサイズを指定します。 |
| -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 [<X>,<Y>] | 多項式決定だけ行います。 |
| -np1 [<X>,<Y>] | 多項式決定のステージ 1 だけ行います。 |
| -np2 | 多項式決定のステージ 2 だけ行います。 |
| -ns [<X>,<Y>] | 篩だけ行います。 |
| -nc | combining だけ行います。 |
| -nc1 [<X>,<Y>] | filtering だけ行います。 |
| -nc2 | linear algebra だけ行います。 |
| -ncr | linear algebra を前回のチェックポイントから再開します。 |
| -nc3 [<X>,<Y>] | square root だけ行います。 |
Ctrl-C で分解を中断できます。中間ファイル msieve.dat が残っているとき直前に中断した分解を途中から再開できます。
オプションを指定しなければ結果はログファイル msieve.log に追記されます。
使用例
63 桁の数 1063-9 が 18 秒で分解できました。
~/msieve-svn/msieve/trunk> ./msieve -e -p -q -v "10^63-9"
Msieve v. 1.48
Tue Sep 21 18:52:00 2010
random seeds: ac326af9 e960b119
factoring 999999999999999999999999999999999999999999999999999999999999991 (63 digits)
searching for 15-digit factors
commencing quadratic sieve (63-digit input)
using multiplier of 1
using 64kb Opteron sieve core
sieve interval: 6 blocks of size 65536
processing polynomials in batches of 17
using a sieve bound of 105107 (5000 primes)
using large prime bound of 5255350 (22 bits)
using trial factoring cutoff of 22 bits
polynomial 'A' values have 8 factors
sieving in progress (press Ctrl-C to pause)
5281 relations (2318 full + 2963 combined from 24414 partial), need 5096
5281 relations (2318 full + 2963 combined from 24414 partial), need 5096
sieving complete, commencing postprocessing
begin with 26731 relations
reduce to 7818 relations in 2 passes
attempting to read 7818 relations
recovered 7818 relations
recovered 6062 polynomials
attempting to build 5280 cycles
found 5280 cycles in 1 passes
distribution of cycle lengths:
length 1 : 2317
length 2 : 2963
largest cycle: 2 relations
matrix is 5000 x 5280 (0.6 MB) with weight 145729 (27.60/col)
sparse part has weight 145729 (27.60/col)
filtering completed in 3 passes
matrix is 4671 x 4735 (0.6 MB) with weight 128105 (27.05/col)
sparse part has weight 128105 (27.05/col)
commencing Lanczos iteration
memory use: 0.6 MB
lanczos halted after 75 iterations (dim = 4666)
recovered 61 nontrivial dependencies
prp32 factor: 14499216344898896752959323769763
prp32 factor: 68969244696581083712684424134557
elapsed time 00:00:18
~/msieve-svn/msieve/trunk>