GMP-ECM は ECM (Elliptic Curve Method; 楕円曲線法) を用いる標準的な素因数分解プログラムです (オプションで P-1 法や P+1 法も選択できます)。小さな素因数を手早く抽出することができるので、SIQS 法や NFS 法の前処理として、あるいは SIQS 法や NFS 法を適用するには大きすぎる合成数を分解したいときに利用されています。
GMP-ECM は GMP を使用します。GMP の使い方 を参照して Cygwin と GMP をインストールしておきます。
補足 : GMP を更新したときは GMP-ECM を再インストールします。
これを書いている時点で GMP-ECM の最新版は 7.0.4 です。
以下の作業は Cygwin64 Terminal で行います。
古いバージョンがインストールされているときは新しいバージョンをインストールする前に古いバージョンをアンインストールしておきましょう。
~> cd ~/ecm-7.0.3 ~/ecm-7.0.3> make uninstall ~/ecm-7.0.3> cd ~ ~>
GMP-ECM はソースコードの形で配布されています。InriaForge: GMP-ECM (Elliptic Curve Method): Project Home の Download からソースコードのアーカイブ ecm-7.0.4.tar.gz を C:\cygwin64\home\ユーザ名 にダウンロードします。
アーカイブを展開します。
~> 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 のインストールは完了です。
GMP-ECM はパラメータ B1 をコマンドラインに書き、分解したい合成数を標準入力から入力します。
~> echo 合成数 | ecm -c 繰り返す回数 パラメータB1
| -c 繰り返す回数 | 指定した回数だけ繰り返します。 |
| -pm1 | P-1 法を使います。 |
| -pp1 | P+1 法を使います。 |
| -one | -c を指定したとき素因数が 1 つ見つかったらそこで終了します。 |
| -h | 使い方を表示します。 |
ここに書かなかったオプションは ecm -h で確認できます。
ECM は確率的な手法なので同じパラメータで何度も繰り返し分解を試みます。B1 を大きくすると大きな素因数が見つかる可能性が高くなりますが、時間もかかるようになります。ある B1 で繰り返してみて素因数が見つからないときは SIQS 法や NFS 法を用いた場合にかかる時間を考えて B1 を増やすか他の手法を用いるか決めます。
| 未知の素因数の桁数 | B1 | 繰り返す回数と発見できる確率 | ||
| 63% | 86% | 95% | ||
| 20 | 11000 | 74 | 148 | 222 |
| 25 | 50000 | 214 | 428 | 642 |
| 30 | 250000 | 430 | 860 | 1290 |
| 35 | 1000000 | 904 | 1808 | 2712 |
| 40 | 3000000 | 2350 | 4700 | 7050 |
| 45 | 11000000 | 4480 | 8960 | 13440 |
| 50 | 43000000 | 7553 | 15106 | 22659 |
| 55 | 110000000 | 17769 | 35538 | 53307 |
| 60 | 260000000 | 42017 | 84034 | 126051 |
| 65 | 850000000 | 69408 | 138816 | 208224 |
~> 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