| STUDIO KAMADA | Japanese to English by @nifty |
| GMP-ECMの使い方 | 2008-06-04(Wed) 20:26 |
|---|
GMP-ECMはECM（Elliptic Curve Method; 楕円曲線法）を用いる標準的な素因数分解プログラムです（オプションでP-1法やP+1法も選択できます）。小さな素因数を手早く抽出することができるので、SIQS法やNFS法の前処理として、あるいはSIQS法やNFS法を適用するには大きすぎる合成数を分解したいときに利用されています。
GMP-ECMはGMPを使用します。GMPの使い方を参照してCygwinとGMPをインストールしておきます。
これを書いている時点でGMP-ECMの最新版は6.2.1です。
古いバージョンがインストールされているときは新しいバージョンをインストールする前に古いバージョンをアンインストールしておきましょう。
~> cd ecm-6.2 ~/ecm-6.2> make uninstall ~/ecm-6.2> cd .. ~>
GMP-ECMはソースコードの形で配布されています。InriaGforge: GMP-ECM (Elliptic Curve Method): Project Infoからソースコードのアーカイブecm-6.2.1.tar.gzをダウンロードしてきて展開します。
~> tar zxf ecm-6.2.1.tar.gz ~> cd ecm-6.2.1 ~/ecm-6.2.1>
./configureを実行します。
~/ecm-6.2.1> ./configure
makeします。小さいプログラムなのでさほど時間はかかりません。
~/ecm-6.2.1> make
make checkします。少し時間がかかります。
~/ecm-6.2.1> make check
チューニングします。関係のないアプリケーションはなるべく終了してから行いましょう。
~/ecm-6.2.1> make ecm-params; make
make installします。
~/ecm-6.2.1> make install
これでECMのインストールは完了です。
GMP-ECMはパラメータB1をコマンドラインに書き、分解したい合成数を標準入力から入力します。
~> echo 合成数 | ecm -c 繰り返す回数 パラメータB1
-c 繰り返す回数-pm1-pp1-one-cを指定したとき素因数が1つ見つかったらそこで終了します。-n-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 6.2.1 [powered by GMP 4.2.2] [ECM]
Input number is 6178425187356575393163579984862080648264153656607846550733734010999716180061 (76 digits)
...snip...
Run 5 out of 214:
Using B1=50000, B2=12746592, polynomial x^2, sigma=1431193006
Step 1 took 719ms
********** Factor found in step 1: 669060346041879059651
Found probable prime factor of 21 digits: 669060346041879059651
Probable prime cofactor 9234481200250125127176894322385720240709107656511138911 has 55 digits
~>
| Copyright (C) 1999-2008 Makoto Kamada All Rights Reserved. | Return from mirror |
|
|