Concept
Integer factorization
Related concepts (31)
Pollard's rho algorithm
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 smallest prime factor of the composite number being factorized. The algorithm is used to factorize a number , where is a non-trivial factor. A polynomial modulo , called (e.g., ), is used to generate a pseudorandom sequence. It is important to note that must be a polynomial.