Editing Pollard's rho algorithm (section)

== Example: factoring {{mvar|n}} = 10403 = 101 · 103 ==

The following table shows numbers produced by the algorithm, starting with <math>x=2</math> and using the polynomial <math>g(x) = (x^2 + 1) \bmod 10403</math>.
The third and fourth columns of the table contain additional information not known by the algorithm.
They are included to show how the algorithm works. 

{| class="wikitable" style="text-align:right;"
! {{tmath|x}} !! {{tmath|y }} !! {{tmath|x \bmod 101}} !! {{tmath|y \bmod 101}} !! step
|-
| 2 || 2 || 2 || 2 || 0
|-
| 5 || 2 || 5 || 2 || 1
|-
| 26 || 2 || 26 || 2 || 2
|-
| 677 || 26 || 71 || 26 || 3
|-
| 598 || 26 || 93 || 26 || 4
|-
| 3903 || 26 || 65 || 26 || 5
|-
| 3418 || 26 || 85 || 26 || 6
|-
| 156 || 3418 || 55 || 85 || 7
|-
| 3531 || 3418 ||{{rh|align=right}}| 97 || 85 || 8
|-
| 5168 || 3418 || 17 || 85 || 9
|-
| 3724 || 3418 || 88 || 85 || 10
|-
| 978 || 3418 || 69 || 85 || 11
|-
| 9812 || 3418 || 15 || 85 || 12
|-
| 5983 || 3418 || 24 || 85 || 13
|-
| 9970 || 3418 || 72 || 85 || 14
|-
| 236 || 9970 || 34 || 72 || 15
|-
| 3682 || 9970 || 46 || 72 || 16
|-
| 2016 || 9970 ||{{rh|align=right}}| 97 || 72 || 17
|-
| 7087 || 9970 || 17 || 72 || 18
|-
| 10289 || 9970 || 88 || 72 || 19
|-
| 2594 || 9970 || 69 || 72 || 20
|-
| 8499 || 9970 || 15 || 72 || 21
|-
| 4973 || 9970 || 24 || 72 || 22
|-
| 2799 || 9970 ||{{rh|align=right}}| 72 || '''72''' || 23
|}

The first repetition modulo 101 is 97 which occurs in step 17. The repetition is not detected until step 23, when <math>x \equiv y \pmod{101}</math>. This causes <math>\gcd (x - y, n) = \gcd (2799 - 9970, n)</math> to be <math>p = 101</math>, and a factor is found.