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の使い方

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

1. Msieveのインストール

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

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

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

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

~> tar zxf msieve141.tar.gz
~> cd msieve-1.41
~/msieve-1.41>

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

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

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

2. Msieveの使い方

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

~/msieve-1.41> ./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.41> ./msieve -e -p -q -v "10^63-9"


Msieve v. 1.41
Wed Apr 15 02:27:43 2009
random seeds: 77606143 cc5c1434
factoring 999999999999999999999999999999999999999999999999999999999999991 (63 di
gits)
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)
5120 relations (2328 full + 2792 combined from 23906 partial), need 5096
5120 relations (2328 full + 2792 combined from 23906 partial), need 5096
sieving complete, commencing postprocessing
begin with 26234 relations
reduce to 7561 relations in 2 passes
attempting to read 7561 relations
recovered 7561 relations
recovered 5870 polynomials
attempting to build 5120 cycles
found 5120 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 2328
   length 2 : 2792
largest cycle: 2 relations
matrix is 5000 x 5120 (0.6 MB) with weight 140163 (27.38/col)
sparse part has weight 140163 (27.38/col)
filtering completed in 3 passes
matrix is 4595 x 4659 (0.6 MB) with weight 126104 (27.07/col)
sparse part has weight 126104 (27.07/col)
commencing Lanczos iteration
memory use: 0.8 MB
lanczos halted after 74 iterations (dim = 4593)
recovered 64 nontrivial dependencies
prp32 factor: 14499216344898896752959323769763
prp32 factor: 68969244696581083712684424134557
elapsed time 00:00:13

~/msieve-1.41>