GGNFSの使い方

GGNFSの使い方	2007-12-21(Fri) 23:10

GGNFSはNFS法（the Number Field Sieve method; 数体ふるい法）を用いる素因数分解プログラムです。SNFS法（the Special Number Field Sieve method; 特殊数体ふるい法）とGNFS法（the General Number Field Sieve method; 一般数体ふるい法）の両方に対応しています。作者はChris Monicoさんです。

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

1. GGNFSのインストール

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

これを書いている時点でリリースされているGGNFSの最新版は0.77.1-20060513です。

GGNFSはソースコードの形で配布されています。SourceForge.net: GGNFS suiteからソースコードのアーカイブggnfs-0.77.1-20060513.tar.bz2をダウンロードしてきて展開します。

~> tar jxf ggnfs-0.77.1-20060513.tar.bz2
~> cd ggnfs
~/ggnfs>

アーカイブを展開したら、テキストエディタを使って~/ggnfs/src/Makefileの7行目にある

次にmakeします。GGNFSのMakefileはコマンドラインで環境を選択します。例えばPentium 4ならば

~/ggnfs> make pentium4

とします。選択できるターゲットについてはMakefileを参照してください。

参考までに、開発者向けの最新版のインストール手順も書いておきます。0.77.1-20060513が期待通りに動作しない場合はこれを試してみるとうまくいくかも知れません。

~> mkdir ~/ggnfs-svn
~> cd ~/ggnfs-svn
~/ggnfs-svn> svn co https://ggnfs.svn.sourceforge.net/svnroot/ggnfs ggnfs
Error validating server certificate for 'https://ggnfs.svn.sourceforge.net:443':
（中略）
(R)eject, accept (t)emporarily or accept (p)ermanently? p
A    ggnfs/trunk
A    ggnfs/trunk/contrib
（中略）
A    ggnfs/tags/release-tag/src/ecm4c.c
A    ggnfs/tags/release-tag/Makefile
Checked out revision 270.
~/ggnfs-svn> cd ggnfs/trunk
~/ggnfs-svn/ggnfs/trunk> make pentium4（Pentium 4のとき）またはmake nocona（Core 2のとき）
make[1]: Entering directory `/home/makoto/ggnfs-svn/ggnfs/trunk'
echo "#define GGNFS_VERSION \"0.77.1-20060722-pentium4\"" > include/version.h
（中略）
make[2]: Leaving directory `/home/makoto/ggnfs-svn/ggnfs/trunk/src'
make[1]: Leaving directory `/home/makoto/ggnfs-svn/ggnfs/trunk'
~/ggnfs-svn/ggnfs/trunk>

2. GGNFSの使い方

GGNFSはメモリを食います。メモリが512MBのとき仮想メモリを使ってもSNFS法で170桁前後が限界のようです。ハードディスクの空き容量は2GB以上あったほうがよいでしょう。

GGNFSを適用する前に小さい素因数をGMP-ECMで搾り出しておきます。GMP-ECMについてはGMP-ECMの使い方を参照してください。

1. 作業ディレクトリを作る

GGNFSは素因数分解の過程で多数の中間ファイルを作るので、個々の分解ごとに作業ディレクトリを用意します。ディレクトリの名前は何でもかまいませんが、分解したい数がわかりやすいものがよいでしょう。以下では4×10¹¹⁷+1を分解する例として名前を40001_117にしています。

~> mkdir 40001_117
~> cd 40001_117
~/40001_117> cd 40001_117

2. 作業ディレクトリにfactLat.plをコピーする

~/40001_117> cp ~/ggnfs/tests/factLat.pl .

3. factLat.plを修正する

テキストエディタを使ってfactLat.plの3行目に書かれているGGNFSのバイナリのパス

$GGNFS_BIN_PATH="../../bin";

を作業ディレクトリとGGNFSのディレクトリの位置関係に合わせて修正します。ここで相対パスの深さに注意します。なお、作業ディレクトリをtestsの直下に作った場合はこの修正は不要です。

$GGNFS_BIN_PATH="../ggnfs/bin";

$GGNFS_BIN_PATH="../ggnfs-svn/ggnfs/trunk/bin";

さらに、factLat.plの1565行目付近にあるプロットルーチンの呼び出し

GGNFSを動かしながら他の作業も行いたい場合はGGNFSの基本優先度を下げます。只今名称未設定さんによると優先度を下げないとCtrl-Cが効かない場合があるようです。factLat.plの58行目付近でコメントアウトされている優先度を下げる設定

# Run the binaries at low priority?
#$NICE="nice -n 19 ";

# Run the binaries at low priority?
$NICE="nice -n 19 ";

のように有効にするとGGNFSの基本優先度が通常以下になります。

4. 入力ファイルを作る

作業ディレクトリの中に素因数分解する数を指示するための入力ファイルを作ります。SNFS法を利用する場合とGNFS法を利用する場合で入力ファイルの作り方が異なります。

SNFS法を利用する場合

4×10¹¹⁷+1のように分解したい数が簡単な式で表せる場合はSNFS法を利用します。SNFS法を利用するときは拡張子.polyのファイルで分解したい数と多項式を指示します。

まず、分解したい数nで割り切れるなるべく単純な5次多項式を考えます。例えば、n = 4·10¹¹⁷+1のときは、2·n = 8·10¹¹⁷+2 = 25·(2·10²³)⁵+2ですから、m = 2·10²³とおくと2·n = 25·m⁵+2となってnで割り切れるmに関する5次多項式ができます。これを40001_117.polyというファイルに次のように記述します。nは分解する数、mは多項式の根、c5とc0は多項式の5次の係数と0次の係数（すなわち定数項）です。

n: 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
m: 200000000000000000000000
c5: 25
c0: 2
skew: 0.60
type: snfs

skewは次の方法で求めます。2と25と5の部分はそれぞれ定数項（c0）と最高次の係数（c5）と多項式の次数です。

~/40001_117> perl -e "printf('%.2f',abs(2/25)**(1/5))"
0.60

なお、多項式の桁数が105桁程度までならば5次多項式よりも4次多項式のほうが速いことがあります。GGNFSは6次多項式まで対応していますが、桁数が多くても（1台のPCで分解できる程度の数ならば）6次多項式よりも5次多項式のほうが効率がよいようです。奇数次にしにくい場合（指数部分がおよそ2対1の項が共存しているとき）は4次多項式または6次多項式にします。

上記のように多項式から拡張子.polyのファイルを考えるのは少々面倒なので、Factorizations of near-repdigit numbersでは未分解の合成数に対して拡張子.polyのファイルを自動生成することですぐに分解を始められるようにしています。Wantedのページで「SUBMIT/RESERVE」をクリックしてみてください。表示を日本語にするにはページの左上の「Japanese」をクリックします。

GNFS法を利用する場合

多項式を見つけることが困難な場合や、GMP-ECMによって多項式の桁数の3割以上を占める素因数が見つかっている場合はGNFS法を利用します。GNFS法を利用するときは拡張子.nのファイルで分解したい数を指示します。

例えばn = 4·10¹¹⁷+1の場合は（これはSNFS法を使うべきですが、あえてGNFS法の書き方をするならば）40001_117.nというファイルに次のように記述します。

n: 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

5. 素因数分解を始める

拡張子.polyのファイルまたは拡張子.nのファイルができたら、factLat.plを実行します。シングルコアの場合（Pentium 4など）とデュアルコアやクワッドコアの場合（Core 2 Duoなど）で手順が少し違います。

シングルコアの場合

シングルコアの場合（Pentium 4など）は、Cygwinのウインドウを1つ開きます。

作業ディレクトリに移動して、factLat.plのパラメータに拡張子を除いた入力ファイル名を書いて実行します。

~> cd 40001_117
~/40001_117> ./factLat.pl 40001_117

デュアルコアやクワッドコアの場合

デュアルコアの場合（Core 2 Duoなど）は、Cygwinのウインドウを2つ開きます。

一方のウインドウで、作業ディレクトリに移動して、factLat.plのパラメータに拡張子を除いた入力ファイル名とクライアント番号1とクライアント数2を書いて実行します。

~> cd 40001_117
~/40001_117> ./factLat.pl 40001_117 1 2

続けて他方のウインドウで、作業ディレクトリに移動して、factLat.plのパラメータに拡張子を除いた入力ファイル名とクライアント番号2とクライアント数2を書いて実行します。

~> cd 40001_117
~/40001_117> ./factLat.pl 40001_117 2 2

クワッドコアの場合も同様にCygwinのウインドウを4つ開いてクライアント番号とクライアント数を1 4、2 4、3 4、4 4とします。

6. 分解が終わるまで待つ

あとは分解が終わるまで待つだけです。上の例ならばs117-40001_117.txtというサマリファイルに結果が出力されます。Pentium 4 3.06GHz, Windows XP and Cygwinの環境で4·10¹¹⁷+1の分解に1時間半くらいかかりました。

s117-40001_117.txt

Number: 40001_117
N=4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
  ( 118 digits)
SNFS difficulty: 117 digits.
Divisors found:
 r1=4164125225093709812091452961256189013773247773370698915379 (pp58)
 r2=960585905509117746404238452290739780153822354353075575508219 (pp60)
Version: GGNFS-0.77.1-20060722-pentium4
Total time: 1.55 hours.
Scaled time: 1.36 units (timescale=0.878).
Factorization parameters were as follows:
n: 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
m: 200000000000000000000000
c5: 25
c0: 2
skew: 1
type: snfs
qintsize: 20000
Factor base limits: 600000/800000
Large primes per side: 3
Large prime bits: 25/25
Max factor residue bits: 46/46
Sieved algebraic special-q in [400000, 520001)
Primes: RFBsize:49098, AFBsize:63608, largePrimes:2109394 encountered
Relations: rels:2202276, finalFF:250358
Max relations in full relation-set: 32
Initial matrix: 112770 x 250358 with sparse part having weight 21934597.
Pruned matrix : 81492 x 82119 with weight 4543937.
Total sieving time: 1.37 hours.
Total relation processing time: 0.06 hours.
Matrix solve time: 0.09 hours.
Time per square root: 0.03 hours.
Prototype def-par.txt line would be:
snfs,117,5,0,0,0,0,0,0,0,0,600000,800000,25,25,46,46,2.4,2.4,50000
total time: 1.55 hours.
 --------- CPU info (if available) ----------