以下のようなページを見つけた。
これが恐ろしく早い。
DB に登録済みなんか!?ってレベルで。
まず、以下のようにして 64bit の合成数を作成する。
これを Intel Core i7-920 と Windows 7 Ultimate 64bit により以下のバージョンの Cygwin64 上の Ruby を使い因数分解を試みた。
ここまではまだ良い。
同様にして、以下のような 128bit の合成数を得た。
これ自体は、場合の数が 2^64 倍に増えているんだから当然と言えば当然である。
ところが、上記のサイトは相変わらず数秒と待たずに結果が返ってくるのである
恐るべし。
アルゴリズムについては言及されてないんだけど、どうなってんだ?これ?
リチャード・ブレントによる変形 かなぁ?
2016-12-26 追記:
リチャード・ブレントによる変形も実装してみたけど、メモリ食い潰し続けて 4GB に達した辺り落ちる orz
パッと見、メモリリークしてそうな気はしないんだけどなぜだ?
これが恐ろしく早い。
DB に登録済みなんか!?ってレベルで。
まず、以下のようにして 64bit の合成数を作成する。
openssl genrsa -out seckey 64 && openssl rsa -in seckey -noout -text例えば以下のような結果が得られた。
Private-Key: (64 bit) modulus: 11297479344276717331 (0x9cc8b59b64ed3f13) publicExponent: 65537 (0x10001) privateExponent: 4865688874707832929 (0x438666408487d061) prime1: 3461747243 (0xce56122b) prime2: 3263519417 (0xc2855ab9) exponent1: 1133914095 (0x439627ef) exponent2: 2928238945 (0xae896161) coefficient: 3348635651 (0xc7982003)prime1 * prime2 が modulus である。
これを Intel Core i7-920 と Windows 7 Ultimate 64bit により以下のバージョンの Cygwin64 上の Ruby を使い因数分解を試みた。
$ uname -a CYGWIN_NT-6.1 EX58EXTREME 2.6.0(0.304/5/3) 2016-08-31 14:32 x86_64 Cygwin $ ruby -v ruby 2.2.5p319 (2016-04-26 revision 54774) [x86_64-cygwin]まず Ruby の Prime.prime_division でやると 10 分以上かかる。
$ time ruby -rprime -e 'p Prime.prime_division 11297479344276717331' [[3263519417, 1], [3461747243, 1]] real 10m36.352s user 10m30.818s sys 0m0.488sポラード・ロー素因数分解法 を実装してみたところ、1 秒とかからず済んでしまう。
$ time ./pollards_rho_algorithm.rb 11297479344276717331 3263519417 real 0m0.816s user 0m0.400s sys 0m0.334sこれを上記の「数の帝国」の web ページでやるとやはり 2 秒とかからず返ってくる。
ここまではまだ良い。
同様にして、以下のような 128bit の合成数を得た。
$ openssl genrsa -out seckey2 128 && openssl rsa -in seckey2 -noout -text Generating RSA private key, 128 bit long modulus .+++++++++++++++++++++++++++ .+++++++++++++++++++++++++++ e is 65537 (0x10001) Private-Key: (128 bit) modulus: 00:b6:31:48:ce:5d:08:e8:be:e6:7f:49:d4:13:c5: a2:4f publicExponent: 65537 (0x10001) privateExponent: 08:11:4a:9e:08:b4:9a:49:b6:9d:f8:0e:8c:9d:a3: 11 prime1: 15857629489502680637 (0xdc119e00dd90f63d) prime2: 15271853502600892283 (0xd3f085d8cc54cf7b) exponent1: 6939058829362922857 (0x604c7d3d97b70569) exponent2: 1594366871611384485 (0x16205438f00c22a5) coefficient: 11163986098413291206 (0x9aee72350952c6c6) $ ruby -e 'p 15857629489502680637*15271853502600892283' 242175394462208712711471431076586824271すると、今度は、ポラード・ロー素因数分解法ですら 24 時間経っても結果が返ってこない。
これ自体は、場合の数が 2^64 倍に増えているんだから当然と言えば当然である。
ところが、上記のサイトは相変わらず数秒と待たずに結果が返ってくるのである
恐るべし。
アルゴリズムについては言及されてないんだけど、どうなってんだ?これ?
リチャード・ブレントによる変形 かなぁ?
2016-12-26 追記:
リチャード・ブレントによる変形も実装してみたけど、メモリ食い潰し続けて 4GB に達した辺り落ちる orz
パッと見、メモリリークしてそうな気はしないんだけどなぜだ?
$ time ./richard_p_brent_algorithm.rb 242175394462208712711471431076586824271 GNU MP: Cannot allocate memory (size=8) Aborted (core dumped) real 5m56.176s user 5m50.542s sys 0m1.223s
タグ
コメントをかく