GGNFSの使い方
※「Studio Kamada」さんに、（GMP-ECMなども含め）導入までの流れを詳しく解説したページが追加されました。
こちらよりずっと詳しく、ずっと正確なはず。そちらをご覧になることをお勧めします。
ある程度(100桁弱以上？)の合成数を素因数分解するのに現在最速(らしい)ソフト、GGNFS。久しぶりに使おうとして戸惑った自分のため、また使ってみたいがイマイチ分からない方の為に、使用までの流れを簡単に。
※GGNFSを使う前には、小さい素因数を他のプログラムで探索してからにしましょう。
自分のとった方法：WindowsXP Homeマシンにて。
「Cygwinのインストール」→「GGNFSの準備(コンパイル)」→
「合成数を入力した設定ファイル作成」→「後はスクリプトにお任せ」
便利な世の中になったものです。初期準備さえ出来れば(単一PCでの計算なら)用意されたスクリプト(factlat.pl)で分解まで全自動。
ちなみに最初の文でお分かりかと思いますが、私Cygwin側もGGNFS側も詳しくないので、以下の流れから外れた部分はほとんど分かりませんのであしからず……。
----------------------------------------
１．Cygwinのインストール
他のCygwin解説サイトを参考に……。
■ Cygwinのサイトから「setup.exe」を取ってきて、実行。
基本的には初期設定のままで良い筈ですが、途中のファイル選択画面にて「Devel」「Math」の右にある「Default」をクリックし、「Install」に変更して下さい。GGNFSコンパイルに必要なファイル(GMPなど含む)を入手できます。
また、GGNFSのドキュメント(pdf形式)が必要な場合は、「view」ボタンを押してFull表示に変更し、「tetex」で始まるパッケージを全てインストールすると良い、のかもしれません(間違っているかも)。
なお、c:\cygwin\binにパスを通すことで、コマンドプロンプトでGGNFSを動かせるようになったりします。
２－１．GGNFSの準備
■ GGNFSをダウンロードしてくる。各バージョンに2つのコンパイル済みパッケージが有りますが、スクリプト類は含まれていません。そちらを使用する場合は同日付のソースも併せて入手することをお勧めします。(※ちなみに開発した方のサイトはこちら)
ところで私は最新バージョン(20060513)のコンパイルでエラー発生、コンパイル済の使用はシャクだった 回避する技術が無かった為に前バージョンを使用しています。
■ ファイルを解凍します。ダウンロードしたファイルは『c:\cygwin\home\(ユーザー名)\』に入れると分かりやすいかもしれません。
cygwinを起動し、上記の場所ならそのまま、他の場所ならばcdコマンドで移動します。Cygwinの場合、Cドライブのルートが「/cygdrive/c/」になります。
例：c:\temp1\temp2 にある場合
次に以下で解凍します。
成功すると、「ggnfs」フォルダが作成されます。
２－２ａ．コンパイル
■ ggnfsフォルダに移動し、
と入力すると、「オプション cpu種類」の一覧表が表示されます。この内1つを選び、例えば
と入力すると Pentium M に最適化された実行ファイル群が「ggnfs」下の「bin」フォルダ内に出来上がります。
■ pdfドキュメントは別にコンパイルする必要があります。
でggnfs\docフォルダに出来上がります。
２－２ｂ．コンパイル済みファイルの解凍
■ ダウンロードした「ggnfs- … .exe」を(Windows上で)実行すると解凍先を聞かれるので、２－２ａと同じく「ggnfs\bin」フォルダを指定して「Install」を押してください。
２－３．Factlat.pl の書き換え
■ Factlat.plは「tests」フォルダ内にあります。使用前に、環境に合わせて少々の書き換えが必要です。
なお、行の先頭に#を書くとコメント行(動作に影響しない)になります。
◆ 「$GGNFS_BIN_PATH=」はGGNFSのファイル位置を指定します。
初期設定では「../../bin」で、常にggnfsの２つ下のフォルダから(例えば「ggnfs\tests」の下にフォルダを作成して)計算する場合にはこのまま。
もしくはフルパスで指定すると安心です。「$GGNFS_BIN_PATH="/cygdrive/c/ … /ggnfs/bin"」のように。
◆ 「$SYS_BIN_PATH=」はcygwin側のbinフォルダの位置を指定。１．でパスを通していない場合はここでの指定が必要(と思われます)。
◆ 「$NICE="nice -n 19 "」は60行前後の所に。コメントアウトされていますが、#を取ってください。そのままでは優先度の関係なのか、「ctrl-c」で一時停止が出来なくなります。
３．合成数を入力した設定ファイル作成
■ 大きく「一般的な数(general numbers)」「簡単な式で表される数(special numbers)」の2つに分かれます。
３－１．「一般的な数」
■以下の1行を書いたファイルを拡張子.n(例えば「test.n」)で保存します。()は無しで。
このファイルとFactlat.plを同じフォルダに保存します。ちなみにこの形式の場合「簡単な式で～」より時間が掛かり、桁数を3～4割増した物と同等程度でしょうか。
３－２．「簡単な式で表される数」
■c5*m^5 + c4*m^4+ … + c0 (c5, c4, ... , c0：(小さい)係数, m：整数, 最高次数は5次、もしくは4次が良い)
の形で表される数を割り切る数……ややこしいので実例で。以下の例は適当な数値なので注意。
◆ 例：8*10^132+1 = 3^2 * (132桁の合成数) の合成数を分解したい場合
GGNFSのお約束として、大きい次数の係数は小さいほうが良いみたいなので以下のように式を決定しました。
8*10^132+1 = 8*10^2*(10^26)^5+1 = 2^5*5^2*(10^26)^5+1
→(5^3倍)→ (2*5)^5*(10^26)^5+5^3 = (10^27)^5+125
これより c5=1, c4=c3=c2=c1=0, c0=125, m=10^27 となるので、設定ファイルの内容は以下のようになります。これを拡張子.poly(例えば「test.poly」)で保存します。同じフォルダにFactlat.plもコピーしておきます。
値が0の係数は省略可能です。他にも設定できる項目はあるのですが、自動設定に任せたほうが無難です。
「skew」の項目は1以上の実数で、ここを自分でチューニングすることで計算終了までの時間が変わるのですが……面倒ならば、この位係数が小さい場合は1で良いと思います。
ちなみに115桁程度を境に、それ以下なら4次、それ以上なら5次式にするのが望ましいっぽいです。
４．後はスクリプトにお任せ
■ ここまで来れば後は簡単。cygwinを起動し、合成数のファイル(仮に「test.n」か「test.poly」)とFactlat.plのあるフォルダに移動、
で計算開始です。数時間～数日後をお楽しみに。
■ なお、前半はこういった計算が続きます。
これの最中はctrl-cでそこまでの結果を保存してくれるので続きをやるのが簡単ですが、他の計算中は停止させると色々面倒です。特に終了前には止められない計算が数分～数時間続くので、時間には余裕を持って下さい。
----------------------------------------
かなり簡単に書いたつもりですが……、結構な分量、結構な時間になりました。そもそも日本でこのソフトを使う(使っている)人は100人も居ないでしょうし、その中で一番理解していない人かもしれないのにこんなの書いて役に立つのかどうか。
間違い、不明な点などありましたら、コメント欄にお願いいたします。
こちらよりずっと詳しく、ずっと正確なはず。そちらをご覧になることをお勧めします。
ある程度(100桁弱以上？)の合成数を素因数分解するのに現在最速(らしい)ソフト、GGNFS。久しぶりに使おうとして戸惑った自分のため、また使ってみたいがイマイチ分からない方の為に、使用までの流れを簡単に。
※GGNFSを使う前には、小さい素因数を他のプログラムで探索してからにしましょう。
自分のとった方法：WindowsXP Homeマシンにて。
「Cygwinのインストール」→「GGNFSの準備(コンパイル)」→
「合成数を入力した設定ファイル作成」→「後はスクリプトにお任せ」
便利な世の中になったものです。初期準備さえ出来れば(単一PCでの計算なら)用意されたスクリプト(factlat.pl)で分解まで全自動。
ちなみに最初の文でお分かりかと思いますが、私Cygwin側もGGNFS側も詳しくないので、以下の流れから外れた部分はほとんど分かりませんのであしからず……。
----------------------------------------
１．Cygwinのインストール
他のCygwin解説サイトを参考に……。
■ Cygwinのサイトから「setup.exe」を取ってきて、実行。
基本的には初期設定のままで良い筈ですが、途中のファイル選択画面にて「Devel」「Math」の右にある「Default」をクリックし、「Install」に変更して下さい。GGNFSコンパイルに必要なファイル(GMPなど含む)を入手できます。
また、GGNFSのドキュメント(pdf形式)が必要な場合は、「view」ボタンを押してFull表示に変更し、「tetex」で始まるパッケージを全てインストールすると良い、のかもしれません(間違っているかも)。
なお、c:\cygwin\binにパスを通すことで、コマンドプロンプトでGGNFSを動かせるようになったりします。
２－１．GGNFSの準備
■ GGNFSをダウンロードしてくる。各バージョンに2つのコンパイル済みパッケージが有りますが、スクリプト類は含まれていません。そちらを使用する場合は同日付のソースも併せて入手することをお勧めします。(※ちなみに開発した方のサイトはこちら)
ところで私は最新バージョン(20060513)のコンパイルでエラー発生、
■ ファイルを解凍します。ダウンロードしたファイルは『c:\cygwin\home\(ユーザー名)\』に入れると分かりやすいかもしれません。
cygwinを起動し、上記の場所ならそのまま、他の場所ならばcdコマンドで移動します。Cygwinの場合、Cドライブのルートが「/cygdrive/c/」になります。
例：c:\temp1\temp2 にある場合
cd /cygdrive/c/temp1/temp2次に以下で解凍します。
tar jxfv ggnfs-0.77.1-20050930.tar.bz2成功すると、「ggnfs」フォルダが作成されます。
２－２ａ．コンパイル
■ ggnfsフォルダに移動し、
makeと入力すると、「オプション cpu種類」の一覧表が表示されます。この内1つを選び、例えば
make pentium-mと入力すると Pentium M に最適化された実行ファイル群が「ggnfs」下の「bin」フォルダ内に出来上がります。
■ pdfドキュメントは別にコンパイルする必要があります。
cd doc/ggnfs-doc
makeでggnfs\docフォルダに出来上がります。
２－２ｂ．コンパイル済みファイルの解凍
■ ダウンロードした「ggnfs- … .exe」を(Windows上で)実行すると解凍先を聞かれるので、２－２ａと同じく「ggnfs\bin」フォルダを指定して「Install」を押してください。
２－３．Factlat.pl の書き換え
■ Factlat.plは「tests」フォルダ内にあります。使用前に、環境に合わせて少々の書き換えが必要です。
なお、行の先頭に#を書くとコメント行(動作に影響しない)になります。
◆ 「$GGNFS_BIN_PATH=」はGGNFSのファイル位置を指定します。
初期設定では「../../bin」で、常にggnfsの２つ下のフォルダから(例えば「ggnfs\tests」の下にフォルダを作成して)計算する場合にはこのまま。
もしくはフルパスで指定すると安心です。「$GGNFS_BIN_PATH="/cygdrive/c/ … /ggnfs/bin"」のように。
◆ 「$SYS_BIN_PATH=」はcygwin側のbinフォルダの位置を指定。１．でパスを通していない場合はここでの指定が必要(と思われます)。
◆ 「$NICE="nice -n 19 "」は60行前後の所に。コメントアウトされていますが、#を取ってください。そのままでは優先度の関係なのか、「ctrl-c」で一時停止が出来なくなります。
３．合成数を入力した設定ファイル作成
■ 大きく「一般的な数(general numbers)」「簡単な式で表される数(special numbers)」の2つに分かれます。
３－１．「一般的な数」
■以下の1行を書いたファイルを拡張子.n(例えば「test.n」)で保存します。()は無しで。
n: (分解したい合成数)このファイルとFactlat.plを同じフォルダに保存します。ちなみにこの形式の場合「簡単な式で～」より時間が掛かり、桁数を3～4割増した物と同等程度でしょうか。
３－２．「簡単な式で表される数」
■c5*m^5 + c4*m^4+ … + c0 (c5, c4, ... , c0：(小さい)係数, m：整数, 最高次数は5次、もしくは4次が良い)
の形で表される数を割り切る数……ややこしいので実例で。以下の例は適当な数値なので注意。
◆ 例：8*10^132+1 = 3^2 * (132桁の合成数) の合成数を分解したい場合
GGNFSのお約束として、大きい次数の係数は小さいほうが良いみたいなので以下のように式を決定しました。
8*10^132+1 = 8*10^2*(10^26)^5+1 = 2^5*5^2*(10^26)^5+1
→(5^3倍)→ (2*5)^5*(10^26)^5+5^3 = (10^27)^5+125
これより c5=1, c4=c3=c2=c1=0, c0=125, m=10^27 となるので、設定ファイルの内容は以下のようになります。これを拡張子.poly(例えば「test.poly」)で保存します。同じフォルダにFactlat.plもコピーしておきます。
type: snfs
n: (132桁の合成数を計算してここに)
m: 1000000000000000000000000000
c5: 5
c4: 0
c3: 0
c2: 0
c1: 0
c0: 125
skew: 1値が0の係数は省略可能です。他にも設定できる項目はあるのですが、自動設定に任せたほうが無難です。
「skew」の項目は1以上の実数で、ここを自分でチューニングすることで計算終了までの時間が変わるのですが……面倒ならば、この位係数が小さい場合は1で良いと思います。
ちなみに115桁程度を境に、それ以下なら4次、それ以上なら5次式にするのが望ましいっぽいです。
４．後はスクリプトにお任せ
■ ここまで来れば後は簡単。cygwinを起動し、合成数のファイル(仮に「test.n」か「test.poly」)とFactlat.plのあるフォルダに移動、
perl Factlat.pl test(「.n」「.poly」は省略可能)で計算開始です。数時間～数日後をお楽しみに。
■ なお、前半はこういった計算が続きます。
これの最中はctrl-cでそこまでの結果を保存してくれるので続きをやるのが簡単ですが、他の計算中は停止させると色々面倒です。特に終了前には止められない計算が数分～数時間続くので、時間には余裕を持って下さい。
----------------------------------------
かなり簡単に書いたつもりですが……、結構な分量、結構な時間になりました。そもそも日本でこのソフトを使う(使っている)人は100人も居ないでしょうし、その中で一番理解していない人かもしれないのにこんなの書いて役に立つのかどうか。
間違い、不明な点などありましたら、コメント欄にお願いいたします。
この記事へのコメント