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 |
fixed grammar |
||
| (2 intermediate revisions by 2 users not shown) | |||
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.
Line 15 ⟶ 13:
[[File:Pollard rho cycle.svg|thumb|Cycle diagram resembling the Greek letter ''ρ'']]
This is detected by [[Floyd's cycle-finding algorithm]]: two nodes <math>i</math> and <math>j</math> (i.e., <math>x_i</math> and <math>x_j</math>) are kept. In each step, one moves to the next node in the sequence and the other moves forward by two nodes. After that, it is checked whether <math>\gcd(x_i - x_j, n) \ne 1</math>. If it is not 1, then this implies that there is a repetition in the <math>\{x_k \bmod p\}</math> sequence (i.e. <math>x_i \bmod p = x_j \bmod p)</math>. This works because if the <math>x_i \bmod p</math> is the same as <math>x_j \bmod p</math>, the difference between <math>x_i</math> and <math>x_j</math> is necessarily a multiple of <math>p</math>. Although this always happens eventually, the resulting [[greatest common divisor]] (GCD) is a divisor of <math>n</math> other than 1. This may be <math>n</math> itself, since the two sequences might repeat at the same time. In this (uncommon) case the algorithm fails,
== Algorithm ==
Line 57 ⟶ 55:
== Variants ==
In 1980, [[Richard Brent (scientist)|Richard Brent]] published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing [[Floyd's cycle-finding algorithm]] with the related [[Cycle detection#Brent.27s algorithm|Brent's cycle finding method]].<ref>{{cite journal |last=Brent |first=Richard P. |authorlink=Richard Brent (scientist) |year=1980 |title=An Improved Monte Carlo Factorization Algorithm |journal=BIT |volume=20 |issue=2 |pages=176–184 |url=
A further improvement was made by Pollard and Brent. They observed that if <math>\gcd(a,n) > 1</math>, then also <math>\gcd(ab,n) > 1</math> for any positive integer {{tmath|b}}. In particular, instead of computing <math>\gcd (|x-y|,n)</math> at every step, it suffices to define {{tmath|z}} as the product of 100 consecutive <math>|x-y|</math> terms modulo {{tmath|n}}, and then compute a single <math>\gcd(z,n)</math>. A major speed up results as 100 {{math|gcd}} steps are replaced with 99 multiplications modulo {{tmath|n}} and a single {{math|gcd}}. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when {{tmath|n}} is a [[square (algebra)|square]]. But it then suffices to go back to the previous {{math|gcd}} term, where <math>\gcd(z,n)=1</math>, and use the regular ''ρ'' algorithm from there.<ref group="note">Exercise 31.9-4 in CLRS</ref>
| |||