AlgoVerse

Pollard's rho

Find a factor of a composite n with the sequence x² + 1: a slow and a fast pointer run along it until the gcd of their difference with n gives a factor.

Take the sequence x ← x² + 1 (mod n). Modulo an unknown prime factor p of n it has only p possible values, so sooner or later it cycles, making a shape like the Greek letter ρ. By the birthday paradox, the cycle shows up after about √p steps.

Read the full explanation ↓
Input:
n=8051PDF export

8051 = 83 × 97; after three moves the gcd gives the factor 97.

  1. from math import gcd
  4. def pollard_rho(n):
  5. if n % 2 == 0:
  6. return 2
  7. # A fixed start and f(x) = x² + 1 instead of random ones, so a run is always the same.
  8. x = 2
  9. y = 2
  10. d = 1
  11. rows = []
  12. while d == 1:
  13. x = (x * x + 1) % n # tortoise: one step
  14. y = (y * y + 1) % n # hare: two steps
  15. y = (y * y + 1) % n
  16. d = gcd(abs(x - y), n)
  17. rows.append((x, y, d))
  18. if d == n:
  19. return None
  20. return d

Invariant: Modulo any prime factor p of n the sequence eventually cycles (a ρ shape); once x ≡ y (mod p), p divides |x − y|.

Start

x—
y—
d—

The table is still empty.

Local variables

n8051

Orange = changed in this step

Call stack

  1. pollard_rho()line 4
Step 1 of 27
Black = move · Orange = key stepmove: 0/3 · factor: 0/1
    Explanation

    The idea

    Take the sequence x ← x² + 1 (mod n). Modulo an unknown prime factor p of n it has only p possible values, so sooner or later it cycles, making a shape like the Greek letter ρ. By the birthday paradox, the cycle shows up after about √p steps.

    Finding the cycle without knowing p

    Run two pointers along the sequence: x one step and y two steps per round (Floyd's tortoise and hare). When they meet modulo p, p divides |x − y|; so gcd(|x − y|, n) gives a factor of n without knowing p in advance.

    Cost

    About √p ≤ n^¼ steps, far fewer than the √n divisions of trial division. If the gcd reaches n itself, try again with another f or start. Here the start and f are fixed, so a run is always the same.