RSA129をインチキして分解

CodeIQ のマシューさんの出題で、129桁の整数
114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
を素因数分解する問題が出た。
まともに計算すると、高速な素因数分解法でも年単位の時間がかかるはずだが、これは歴史的に有名な問題で、この数自身か「RSA」で検索すれば答はすぐに分かる。

明らかなネタ出題で、カンニングして解答するしかないのだが、一応、汎用的な素因数分解法で、ある程度の計算をした上で解を出力するような体裁にこだわってみた。
下がそのプログラムを少し修正したもの。
言語は Ruby で、素因数分解法は Pollard のρ法(またはモンテカルロ法)。

解が得られるまで、f(x) が 5万回以上呼ばれる。
この回数が大きくなるような @a と @x0 の組を探索するのに丸一日の計算時間がかかった。

# Pollard's rho algorithm
class Rho
  def initialize
    @a = 3201
    # 初期値
    @x0 = 304186103691826151854556738265317916675223405003210318178783835
  end

  def f(x)
    (x ** 2 + @a) % @n
  end

  # n の非自明な因数をひとつ返す
  def factor(n)
    @n = n
    x = y = @x0
    begin
      prod = 1
      100.times do
        x = f(x)
        y = f(f(y))
        prod = prod * (x - y) % n
      end
    end until (2...@n) === (g = @n.gcd(prod))
    g
  end
end

RSA129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

q = Rho.new.factor(RSA129)

# 素因数を出力(RSA129 は2素数の積であることを仮定している)
puts q, RSA129 / q