Skip to main content

Pollard's Rho

By

Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the size of the smallest prime factor of the composite number being factorized.The algorithm takes as its inputs n, the integer to be factored; and g(x), a polynomial in x computed modulo n.The output is either a non-trivial factor of n, or failure


function pollardRho(n)
{
    //Logic
    if (n==1) return n;
  if (n % 2 == 0) return 2;
  var x = (Math.random()%(n-2))+2;
  var y = x;
  var c = (Math.random()%(n-1))+1;
  var d = 1;

  while (d==1)
  {
      x = (power_mod_q(x, 2, n) + c + n)%n;
      y = (power_mod_q(y, 2, n) + c + n)%n;
      y = (power_mod_q(y, 2, n) + c + n)%n;
      d = euclidean(abs(x-y), n);
      if (d==n) return PollardRho(n);
  }
  return d;
}