Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 37 ยท Primality and Factoring

Pollard's Rho Factoring

Factor integers faster than trial division with Pollard's rho: the birthday paradox, Floyd cycle detection, gcd tricks, and a complete Python implementation.

Primality tests tell you that a number is composite, but not what its factors are. Trial division finds a factor p after about p steps, which is hopeless for a 40-digit p. John Pollard's rho method (1975) finds a factor p in about โˆšp steps using almost no memory. It is simple enough to write in ten lines and strong enough to crack 20-digit factors in a blink.

The idea borrows from the birthday paradox. Pick random numbers modulo n. Modulo the unknown factor p, two of them collide after about โˆšp draws, and a collision modulo p that is not a collision modulo n leaks p through a gcd.

The key observation

Let p be an unknown prime factor of n. Suppose x and y are two numbers with x โ‰ก y (mod p) but x โ‰ข y (mod n). Then p divides x - y and also n, so gcd(x - y, n) is a nontrivial divisor of n. We never need to know p: we only compute gcds modulo n and hope that one of them is not 1.

To generate pseudo-random values we iterate a simple polynomial map, usually f(x) = xยฒ + c mod n. Because the sequence modulo p lives in a set of only p values, it must eventually cycle. Drawn on paper, the path has a tail and then a loop, which looks like the Greek letter ฯ.

Python The rho shape modulo a small prime

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the mod 83 line: it settles into a short cycle long before the sequence modulo n repeats. That early cycle is what we exploit.

Floyd's cycle trick

We cannot see the sequence modulo p, so we cannot spot the repeat directly. Floyd's tortoise and hare solves this: keep two copies of the sequence, move the tortoise one step and the hare two steps per round, and compute gcd(|tortoise - hare|, n) each round. Once both are inside the cycle they differ by a multiple of the cycle length modulo p, so at some round they agree modulo p.

Python Pollard rho with Floyd cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each call returns the factor and the number of rounds it took. For the 13-digit number the rounds are only a few hundred, even though trial division would need about a million divisions. If d equals n the tortoise and hare met modulo every prime factor at once and the attempt fails. The cure is to change the constant c (or the start value) and try again.

A complete factorizer

To get the full prime factorization, combine rho with the Miller-Rabin test: test whether the current number is prime, otherwise split it with rho and recurse on both pieces.

Python Factor completely with rho and Miller-Rabin

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last column compares with SymPy's factorint. The number 2**64 + 1 is the sixth Fermat number, F6. It splits into 274177 ร— 67280421310721, a factorization Landry found by hand in 1880.

Brent's improvement and batching gcds

Two cheap upgrades make rho several times faster. Brent's variant uses a power-of-two cycle search that needs fewer evaluations of f than Floyd's. Batching multiplies many differences together modulo n and takes one gcd for the whole batch, because gcds are far more expensive than multiplications. If a batch ends with d == n, step back and redo it one difference at a time.

Python Rho with batched gcds (Brent style)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Timings vary from machine to machine, so we print them only for curiosity; the factor 1000003 or 1000033 is what matters.

Limits

Rho finds a factor p in about โˆšp steps, so it is excellent for factors up to 15 to 20 digits and hopeless against an RSA modulus made of two 150-digit primes. For those, the number field sieve is used. Rho also struggles with perfect powers like pยฒ (check with an integer square root first) and cannot return small factors faster than trial division, so practical programs divide out small primes first.

flowchart LR
    N["n"] --> P{"prime?"}
    P -->|yes| R["record factor"]
    P -->|no| S["rho finds d"]
    S --> L["factor(d)"]
    S --> M["factor(n/d)"]

Recursive factoring: primality test, split, repeat.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Roughly how many steps does Pollard's rho need to find the prime factor p?

    By the birthday paradox, a collision modulo p appears after about sqrt(p) iterations.
  2. 2. Why does gcd(x - y, n) reveal a factor?

    p divides x - y and n, so the gcd is at least p. It is not n because x and y differ modulo n.
  3. 3. What should you do when the rho attempt returns d = n?

    d = n means the collision happened modulo every prime factor at once, which gives no split. A new polynomial usually works.
  4. 4. Why test for primality before running rho?

    If n is prime no nontrivial gcd exists, so rho would loop forever. Test first.

Summary

  • Rho iterates x โ†’ xยฒ + c mod n and looks for a collision modulo an unknown factor p.
  • A gcd of a difference with n reveals p; Floyd's tortoise and hare detects the collision without storing the sequence.
  • Expected cost is about โˆšp steps, so it handles factors of roughly 20 digits.
  • Combine it with a primality test to factor completely, and retry with a new c on failure.
  • Brent's cycle search and batched gcds make it faster in practice.

Next: Fermat's Factorization and Pollard's p-1