Module: FasterPrime::PollardRho

Defined in:
lib/faster_prime/prime_factorization.rb

Overview

An implementation of Pollard’s rho algorithm (Brent’s variant)

en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants

Class Method Summary collapse

Class Method Details

.try_find_factor(n) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/faster_prime/prime_factorization.rb', line 67

def self.try_find_factor(n)
  x0 = rand(n)
  y = x0
  m = Math.log(n, 2).ceil
  c = 2
  r = q = 1
  while true
    x = y
    r.times { y = (y * y + c) % n }
    k = 0
    while true
      ys = y
      [m, r - k].min.times do
        y = (y * y + c) % n
        q = (q * (x - y)) % n
      end
      g = q.gcd(n)
      k += m
      break if k >= r || g > 1
    end
    r *= 2
    break if g > 1
  end
  if g == n
    while true
      ys = (ys * ys + c) % n
      g = (x - ys).gcd(n)
      break if g > 1
    end
  end
  if g == n
    raise Failed, "failed to find a factor: #{ n }"
  else
    g
  end
end