目次

  1. GGNFS とは
  2. GGNFS のインストール
  3. GGNFS の使い方
    1. 作業ディレクトリを作る
    2. 作業ディレクトリに factLat.pl をコピーする
    3. factLat.pl を修正する
    4. 入力ファイルを作る
    5. 素因数分解を始める
    6. 分解が終わるまで待つ

1. GGNFS とは

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

2. 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 行目にある

MATBUILD_TPIE=1

を

MATBUILD_TPIE=0

に変更します。

次に 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>

3. GGNFS の使い方

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

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

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

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

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

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

作業ディレクトリに ggnfs/tests/factLat.pl をコピーしてきます。

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

3.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 の 43 行目付近にあるふるいの設定

$DOCLASSICAL=1;

を

$DOCLASSICAL=0;

に変更します。

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

    plotLP;

を

#    plotLP;

のようにコメントアウトします。

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 の基本優先度が通常以下になります。

3.4. 入力ファイルを作る

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

SNFS 法を利用する場合

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

まず、分解したい数 n で割り切れるなるべく単純な 5 次多項式を考えます。例えば、n = 4·10117+1 のときは、2·n = 8·10117+2 = 25·(2·1023)5+2 ですから、m = 2·1023 とおくと 2·n = 25·m5+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-related numbers では未分解の合成数に対して拡張子 .poly のファイルを自動生成することですぐに分解を始められるようにしています。Wanted list のページで「SUBMIT/RESERVE」をクリックすると表示される説明にしたがってください。表示を日本語にするにはページの右上の「英語 ⇒ 日本語」をクリックします。

GNFS 法を利用する場合

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

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

n: 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

3.5. 素因数分解を始める

拡張子 .poly のファイルまたは拡張子 .n のファイルができたら、factLat.pl を実行します。シングルコアの場合 (fPentium 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 とします。

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

あとは分解が終わるまで待つだけです。上の例ならば s117-40001_117.txt というサマリファイルに結果が出力されます。Pentium 4 3.06GHz, Windows XP and Cygwin の環境で 4·10117+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) ----------