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の使い方	2008-09-25(Thu) 23:20

Msieveのインストール
Msieveの使い方

1. Msieveのインストール

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

MsieveはソースコードとWin32用バイナリの形で配布されています。

ソースコードを利用する場合

Integer Factorization Source Codeからソースコードのアーカイブmsieve138.tar.gzをダウンロードしてきて展開します。

~> tar zxf msieve138.tar.gz
~> cd msieve-1.38
~/msieve-1.38>

makeします。Intel/AMDの32ビット環境は「make x86 ECM=1」、64ビット環境は「make x86_64 ECM=1」、その他は「make generic ECM=1」です。

~/msieve-1.38> make x86 ECM=1（Intel/AMDの32ビット環境のとき）またはmake x86_64 ECM=1（Intel/AMDの64ビット環境のとき）

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

2. Msieveの使い方

Msieveは分解したい数（を表す式）をコマンドラインに書くだけで分解してくれます。式を書くときは"～"で囲みます。

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

コマンドラインオプション

-s 中間ファイル名: 中間ファイル名をmsieve.datから変更します。
-l ログファイル名: ログファイル名をmsieve.logから変更します。
-i 入力ファイル名: 分解したい数をファイルから入力します。
-m: 分解したい数を標準入力から入力します。
-q: ログファイルに出力しません。
-d デッドライン（分）: 指定された時間が経ったら中止します。
-r relationの数の上限: relationの数が上限を超えたら中止します。
-p: 優先度を下げて実行します。
-v: ログを画面に出力します。
-t スレッド数の上限: スレッド数の上限を指定します。
-e: 15桁を超える素因数をECMで探します。
-c: MPQS法のときふるいだけ行います。
-n: 97桁を超える合成数をGNFS法で分解します。
-nf factor baseファイル名: GNFS法のときfactor baseファイル名をmsieve.fbから変更します。
-np [X,Y]: GNFS法のとき多項式決定だけ行います。
-ns [X,Y]: GNFS法のときふるいだけ行います。
-nc: GNFS法のときcombiningだけ行います。
-nc1 [X,Y]: GNFS法のときfilteringだけ行います。
-nc2: GNFS法のときlinear algebraだけ行います。
-ncr: GNFS法のときlinear algebraだけ行って前回のチェックポイントから再開します。
-nc3 [X,Y]: GNFS法のときsquare rootだけ行います。

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

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

使用例

~/msieve-1.38> ./msieve -e -p -q -v "10^63-9"


Msieve v. 1.38
Thu Sep 25 23:16:51 2008
random seeds: 998761c2 82edcf23
factoring 999999999999999999999999999999999999999999999999999999999999991 (63 digits)
searching for 15-digit factors
commencing quadratic sieve (63-digit input)
using multiplier of 1
using 64kb Pentium 4 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)
5179 relations (2292 full + 2887 combined from 24324 partial), need 5096
5179 relations (2292 full + 2887 combined from 24324 partial), need 5096
sieving complete, commencing postprocessing
begin with 26616 relations
reduce to 7680 relations in 2 passes
attempting to read 7680 relations
recovered 7680 relations
recovered 5992 polynomials
attempting to build 5179 cycles
found 5179 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 2292
   length 2 : 2887
largest cycle: 2 relations
matrix is 5000 x 5179 (0.6 MB) with weight 142670 (27.55/col)
sparse part has weight 142670 (27.55/col)
filtering completed in 3 passes
matrix is 4677 x 4741 (0.6 MB) with weight 128749 (27.16/col)
sparse part has weight 128749 (27.16/col)
commencing Lanczos iteration
memory use: 0.8 MB
lanczos halted after 75 iterations (dim = 4674)
recovered 63 nontrivial dependencies
prp32 factor: 14499216344898896752959323769763
prp32 factor: 68969244696581083712684424134557
elapsed time 00:00:30

~/msieve-1.38>