ρヒューリスティック

大きな数の因数を発見的に求めるρ法（Pollardのρヒューリスティック）をRubyで実装しました。

# 2個の素数の積を因数分解する
def factor_two(given)
  start = Time.now
  one = rho(given)
  another = given / one
  elapsed = Time.now - start
  puts "#{given} = #{one} * #{another} (#{elapsed} sec)"
end

# 『アルゴリズムイントロダクション』第3巻p.196
# 「Pollardのρヒューリスティック」で因数を探す
def rho(n)
  i = 1
  x = rand(n)
  y = x
  k = 2
  loop do
    i += 1
    x = (x * x - 1) % n
    f = n.gcd(y - x)
    if f != 1 and f != n
      return f
    elsif i == k
      y = x
      k *= 2
      puts "(i = #{i})"
    end
  end
end

secret = [
  8616460799,
  1441149131980013567,
  193410142322144802270868533101027,
  134502404035572884331085302462570091,
].each do |n|
  factor_two n
end

実行結果です。乱数の具合によって実行時間は大きく変わります。

(i = 2)
(i = 4)
(i = 8)
(i = 16)
(i = 32)
(i = 64)
(i = 128)
8616460799 = 96079 * 89681 (0.02 sec)
(i = 2)
(i = 4)
(i = 8)
(i = 16)
(i = 32)
(i = 64)
(i = 128)
(i = 256)
(i = 512)
(i = 1024)
1441149131980013567 = 524287 * 2748779069441 (0.561 sec)
(i = 2)
(i = 4)
(i = 8)
(i = 16)
(i = 32)
(i = 64)
(i = 128)
(i = 256)
(i = 512)
(i = 1024)
(i = 2048)
(i = 4096)
193410142322144802270868533101027 = 999907 * 193428131138340667952988161 (3.545 sec)
(i = 2)
(i = 4)
(i = 8)
(i = 16)
(i = 32)
(i = 64)
(i = 128)
(i = 256)
(i = 512)
(i = 1024)
(i = 2048)
(i = 4096)
(i = 8192)
(i = 16384)
(i = 32768)
(i = 65536)
134502404035572884331085302462570091 = 695361131 * 193428131138340667952988161 (76.339 sec)