目次

  1. GMP-ECM とは
  2. GMP-ECM のインストール
    1. 古いバージョンをアンインストールする
    2. ソースコードをダウンロードする
    3. インストールする
  3. GMP-ECM の使い方
  4. 使用例

1. GMP-ECM とは

GMP-ECM は ECM (Elliptic Curve Method; 楕円曲線法) を用いる標準的な素因数分解プログラムです (オプションで P-1 法や P+1 法も選択できます)。小さな素因数を手早く抽出することができるので、SIQS 法や NFS 法の前処理として、あるいは SIQS 法や NFS 法を適用するには大きすぎる合成数を分解したいときに利用されています。

2. GMP-ECM のインストール

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

補足: GMP を更新したときは GMP-ECM を再インストールします。

これを書いている時点で GMP-ECM の最新版は 7.0.4 です。

以下の作業は Cygwin64 Terminal で行います。

2.1. 古いバージョンをアンインストールする

古いバージョンがインストールされているときは新しいバージョンをインストールする前に古いバージョンをアンインストールしておきましょう。

~> cd ~/ecm-7.0.3
~/ecm-7.0.3> make uninstall
~/ecm-7.0.3> cd ~
~>

2.2. ソースコードをダウンロードする

GMP-ECM はソースコードの形で配布されています。InriaForge: GMP-ECM (Elliptic Curve Method): Project Home の Download からソースコードのアーカイブ ecm-7.0.4.tar.gz を C:\cygwin64\home\ユーザ名 にダウンロードします。

2.3. インストールする

アーカイブを展開します。

~> tar zxf ecm-7.0.4.tar.gz
~> cd ~/ecm-7.0.4
~/ecm-7.0.4> 

./configure を実行します。自分で make した最新版の GMP は /usr/local に入っているので --with-gmp=/usr/local を付けます。これを付けないと gmp.h と libgmp のバージョンが違うというエラーが出ることがあります。また、x86_64 のときはデフォルトで --enable-asm-redc が指定されますが、これがあると正常に動作しない場合は --disable-asm-redc を指定します。

~/ecm-7.0.4> ./configure --with-gmp=/usr/local --disable-asm-redc

make します。小さいプログラムなのでさほど時間はかかりません。

~/ecm-7.0.4> make

make check します。少し時間がかかります。

~/ecm-7.0.4> make check

make installします。

~/ecm-7.0.4> make install
~/ecm-7.0.4> cd ~
~> 

これで GMP-ECM のインストールは完了です。

3. GMP-ECM の使い方

GMP-ECM はパラメータ B1 をコマンドラインに書き、分解したい合成数を標準入力から入力します。

~> echo 合成数 | ecm -c 繰り返す回数 パラメータB1
ecm のオプション (抜粋)
-c 繰り返す回数指定した回数だけ繰り返します。
-pm1P-1 法を使います。
-pp1P+1 法を使います。
-one-c を指定したとき素因数が 1 つ見つかったらそこで終了します。
-h使い方を表示します。

ここに書かなかったオプションは ecm -h で確認できます。

ECM は確率的な手法なので同じパラメータで何度も繰り返し分解を試みます。B1 を大きくすると大きな素因数が見つかる可能性が高くなりますが、時間もかかるようになります。ある B1 で繰り返してみて素因数が見つからないときは SIQS 法や NFS 法を用いた場合にかかる時間を考えて B1 を増やすか他の手法を用いるか決めます。

未知の素因数の桁数と B1 の関係 (README より)
未知の素因数の桁数B1繰り返す回数と発見できる確率
63%86%95%
201100074148222
2550000214428642
302500004308601290
35100000090418082712
403000000235047007050
45110000004480896013440
504300000075531510622659
55110000000177693553853307
602600000004201784034126051
6585000000069408138816208224

4. 使用例

~> echo 6178425187356575393163579984862080648264153656607846550733734010999716180061 | ecm -c 214 50000
GMP-ECM 7.0.4 [configured with GMP 6.1.1] [ECM]
Input number is 6178425187356575393163579984862080648264153656607846550733734010999716180061 (76 digits)
Using B1=50000, B2=12746592, polynomial x^2, sigma=1:1364681308
Step 1 took 16ms
Step 2 took 47ms
Run 2 out of 214:
Using B1=50000, B2=12746592, polynomial x^2, sigma=1:3050864359
Step 1 took 47ms
Step 2 took 31ms
Run 3 out of 214:
Using B1=50000, B2=12746592, polynomial x^2, sigma=1:2554116968
Step 1 took 31ms
Step 2 took 47ms
Run 4 out of 214:
Using B1=50000, B2=12746592, polynomial x^2, sigma=1:287252085
Step 1 took 31ms
Step 2 took 31ms
********** Factor found in step 2: 669060346041879059651
Found prime factor of 21 digits: 669060346041879059651
Prime cofactor 9234481200250125127176894322385720240709107656511138911 has 55 digits