以下のようなページを見つけた。

• 数の帝国
  • 因数分解
  • 素因数分解

これが恐ろしく早い。
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