Pollard's Rho Algorithm

Website Links For
Rho

Information About

Pollard's Rho Algorithm

Pollard's rho algorithm is a special-purpose Integer Factorization Algorithm . It was invented by John Pollard in 1975 . It is particularly effective at splitting composite numbers with small factors. CORE IDEAS
	The Rho Algorithm Therefore Uses A Function Modulo ''n'' As A Generator Of A Pseudo-random Sequence It Runs One Sequence Twice As "fast" As The Other Ie For Every Iteration Made By One Copy Of The Sequence, The Other Copy Makes Two Iterations Let ''x'' Be The Current State Of One Sequence And ''y'' Be The Current State Of The Other The	"http://wwwinformationdelightinfo/encyclopedia/entry/greatest_common_divisor" class="copylinks">GCD of ''x'' &minus ''y'' and ''n'' is taken at each step If this GCD ever comes to ''n'', then the algorithm terminates with failure, since this means ''x'' = ''y'' and therefore, by Floyd's cycle-finding algorithm, the sequence has cycled and continuing any further would only be repeating previous work
	<tr><td Width	30>''i''</td><td width=60>''x''<sub>''i''</sub></td><td width=60>''y''<sub>''i''</sub></td><td>GCD(''x''<sub>''i''</sub> &minus ''y''<sub>''i''</sub>, 8051)</td></tr>

97 is a non-trivial factor of 8051. Other values of ''c'' may give the cofactor (83) of 97 instead of 97.

REFERENCES

Richard P. Brent . ''An Improved Monte Carlo Factorization Algorithm'', BIT 20, 1980, pp.176-184, http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb051i.pdf

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . '' Introduction To Algorithms '', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.9: Integer factorization, pp.896–901 (this section discusses only Pollard's rho algorithm).