Content deleted Content added
Citation bot (talk | contribs) Add: jstor, issue, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | Category:Integer factorization algorithms | #UCB_Category 16/26 |
Expected runtime proportional to the square root of smallest factor, not its size |
||
Line 1:
{{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 |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]]
== Core ideas ==
| |||