Pollard's rho algorithm

README.ja.md

Pollard's rho algorithm

Original Papers

Pollard's rho algorithm

• J. M. Pollard. "A Monte Carlo method for factorization.", BIT Numerical Mathematics, Volume 15, Issue 3, September 1975, pp.331-334.
  • DOI:10.1007/BF01933667
  • Google Scholar

An improvement by Richard P. Brent

• Richard P. Brent. "An Improved Monte Carlo Factorization Algorithm.", BIT Numerical Mathematics, Volume 20, Issue 2, June 1980, pp.176-184
  • DOI:10.1007/BF01933190
  • Google Scholar

Other References

• Wikipeda / ポラード・ロー素因数分解法
• 高校数学の美しい物語 / 素因数分解の高速なアルゴリズム（ロー法）
• University of Colorado Boulder / Department of Computer Sciense / Prof. Sriram Sankaranarayanan / Discrete Structures (CSCI 2824, Spring 2014) / A Quick Tutorial on Pollard's Rho Algorithm

pollards_rho_algorithm.rb

#!/usr/bin/env ruby

# Pollard's rho algorithm
# @reference
# * [ポラード・ロー素因数分解法](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95)
# * [素因数分解の高速なアルゴリズム（ロー法）](http://mathtrain.jp/rhoalgorithm)
def pollards_rho_algorithm(n)
  f = -> x { (x * x + 1) % n }
  
  x = 2
  y = 2
  d = 1
  
  while d == 1
    x = f.call(x)
    y = f.call(f.call(y))
    d = (x-y).abs.gcd(n)
  end
  d == n ? nil : d
end

puts pollards_rho_algorithm ARGV[0].to_i if File.expand_path($0) == File.expand_path(__FILE__)

richard_p_brent_algorithm.rb

#!/usr/bin/env ruby

# Richard P.Brent algorithm
# @reference
# * [ポラード・ロー素因数分解法](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95)
# * [RICHARD P.BRENT, AN IMPROVED MONTE CARLO FACTORIZATION ALGORITHM](http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb051i.pdf)
def richard_p_brent_algorithm(n)
  f = -> x { (x * x + 3) % n }
  x0 = 0
  m = 1

  y = x0
  r = 1
  q = 1

  begin
    x = y
    r.times{ y = f.call(y) }
    k = 0
    begin
      ys = y
      [m, r - k].min.times{
        y = f.call(y)
        q = (q * (x - y).abs) % n
      }
      g = q.gcd(n)
      k += m
    end until k >= r || g > 1
    r *= 2
  end until g > 1
  if (g == n)
    begin
      ys = f.call(ys)
      g = (x - ys).abs.gcd(n)
    end until g > 1
  end
  g == n ? nil : g
end

puts richard_p_brent_algorithm ARGV[0].to_i if File.expand_path($0) == File.expand_path(__FILE__)