Content deleted Content added
Revert unexplained change by User:Dngnogu in 2020, this is clearly wrong, if a=b, then a-b is zero, not a multiple of p |
Eep, left a test diff template lying around :) |
||
Line 1:
{{Short description|Integer factorization algorithm}}
{{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.
| |||