Pollard’s $\rho $ algorithm
Pollard’s $\rho $ algorithm is an integer factorization algorithm devised by John Pollard in 1975 to take advantage of Floyd’s cyclefinding algorithm and pseudorandom number generation. Theoretically, trial division^{} always returns a result (though of course in practice the computing engine’s resources could be exhausted or the user might not to be around to care for the result). Pollard’s $\rho $ algorithm, on the other hand, was designed from the outset to cope with the possibility of failure to return a result.
It can be left up to the implementer to choose a function $f(x)$ with a finite set^{} of values that can be guaranteed to become cyclic quickly enough after few iterations. Crandall and Pomerance recommend $f(x)={x}^{2}+amodn$, where $n$ is the number to be factored and $a$ is a pseudorandom number chosen based on $n$.
Choose a function $f(x)$ per the given requirements and call Pollard’s $\rho $ algorithm with $n$ a positive integer.

1.
Choose random $a$ and $b$ from the ranges $$ and $$ and set $c=a$ and $d=b$.

2.
Set $g=1$.

3.
While $g==1$ and allowed number of iterations not exceeded, iterate $c=f(c)$ once and $d=f(d)$ twice and compute $g=GCD(cd,n)$. The implementer may choose to take the absolute value^{} of $cd$, though some implementations of GCD don’t mind being given negative arguments^{}.

4.
If $g>1$, it is a factor of $n$. Otherwise, the algorithm has failed.
Take for example, $n=42$. Suppose our dice give us $a=12$ and $b=37$. I promise I didn’t choose these values consciously, but it happens that 37 does not change when input to $f(x)={x}^{2}+12mod42$! 12 will change however, giving a sequence^{} that continues 0, 20, 13. At 13, we find that $3713=24$, and computing $GCD(24,42)$ gives up 6, which is not a prime, but is easily enough taken care of by trial division. The factorization is therefore $42=2\cdot 3\cdot 7$.
To date, the most wellknown success of this algorithm was when Pollard and Richard Brent factored 115792089237316195423570985008687907853269984665640564039457584007913129639937 (the eighth Fermat number) in less than two hours, which was an impressive feat in 1975 for a UNIVAC 1100/42. Today, Mathematica running on a Dell with Windows XP factors that number in about 12 seconds (Mathematica’s FactorInteger
function has always used Pollard’s $\rho $ algorithm as one of the algorithms it uses).
Title  Pollard’s $\rho $ algorithm 

Canonical name  PollardsrhoAlgorithm 
Date of creation  20130322 16:44:22 
Last modified on  20130322 16:44:22 
Owner  PrimeFan (13766) 
Last modified by  PrimeFan (13766) 
Numerical id  5 
Author  PrimeFan (13766) 
Entry type  Algorithm 
Classification  msc 11A41 
Synonym  Pollard $\rho $ algorithm 
Synonym  Pollard’s rho algorithm 
Synonym  Pollard rho algorithm 