Editing Pollard's rho algorithm (section)

== Algorithm ==
The algorithm takes as its inputs {{mvar|n}}, the [[integer]] to be factored; and {{tmath|g(x)}}, a polynomial in {{mvar|x}} computed modulo {{mvar|n}}. In the original algorithm, <math>g(x) = (x^2 - 1) \bmod n</math>, but nowadays it is more common to use <math>g(x) = (x^2 + 1) \bmod n</math>. The output is either a non-trivial factor of {{mvar|n}}, or failure. 

It performs the following steps:<ref name=":0">{{cite book |last1=Cormen |first1=Thomas H. |authorlink=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |authorlink2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |authorlink3=Ronald L. Rivest |last4=Stein |first4=Clifford |authorlink4=Clifford Stein |name-list-style=amp |chapter=Section 31.9: Integer factorization |title=[[Introduction to Algorithms]] |year=2009 |edition=third |publisher=MIT Press |location=Cambridge, MA |pages=975–980|isbn=978-0-262-03384-8 }} (this section discusses only Pollard's rho algorithm).</ref>

Pseudocode for Pollard's rho algorithm
     x ← 2 // starting value
     y ← x
     d ← 1
 
     '''while''' d = 1:
         x ← g(x)
         y ← g(g(y))
         d ← gcd(|x - y|, n)
 
     '''if''' d = n: 
         '''return failure'''
     '''else''':
         '''return''' d

Here {{mvar|x}} and {{mvar|y}} corresponds to {{tmath|x_i}} and {{tmath|x_j}} in the previous section. Note that this algorithm may fail to find a nontrivial factor even when {{mvar|n}} is composite. In that case, the method can be tried again, using a starting value of ''x'' other than 2 (<math>0 \leq x < n</math>)  or a different {{tmath|g(x)}}, <math>g(x) = (x^2 + b) \bmod n</math>, with <math>1 \leq b < n-2</math>.