Pollard's rho algorithm: Difference between revisions

Revision as of 22:09, 27 September 2024

Revision as of 22:11, 27 September 2024

Line 2:

{{about|the integer factorization algorithm|the discrete logarithm algorithm|Pollard's rho algorithm for logarithms}}

'''Pollard's rho algorithm''' is an [[algorithm]] for [[integer factorization]]. It was invented by [[John Pollard (mathematician)|John Pollard]] in 1975.<ref>{{cite journal |last=Pollard |first=J. M. |year=1975 |title=A Monte Carlo method for factorization |url=https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf |journal=BIT Numerical Mathematics |volume=15 |issue=3 |pages=331–334 |doi=10.1007/bf01933667 |s2cid=122775546 }}</ref> 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.

== Core ideas ==