Find a collision modulo an unknown prime
Iterate a pseudorandom map modulo n. The sequence, viewed modulo an unknown prime factor p, must eventually cycle — and by the birthday bound it does so after about √p steps, far sooner than the cycle modulo n. A collision modulo p but not modulo n makes the difference of two terms divisible by p and not by n, so a GCD reveals the factor.
Learning objectives
- Explain the birthday argument giving the √p expected running time.
- Compare Floyd and Brent cycle detection.
- Implement GCD batching and handle its failure mode.
- Recognise when rho is the right tool and when it is not.
- Describe the adaptation to discrete logarithms.
Section 01The idea
Iterate x ↦ x2 + c modulo n. Modulo an unknown prime p dividing n, the sequence takes values in a set of size p and must repeat. By the birthday bound, a repeat occurs after about √p steps — and since p ≤ √n, that is about n1/4 steps.
The shape of the sequence — a tail leading into a cycle — is what gives the method its name.
The collision happens modulo p, which is unknown, and is detected only through the GCD. The algorithm never observes the residues it is actually exploiting — an unusually elegant piece of indirection.
Section 02Cycle detection
- Choose a random c ≠ 0, −2 and set x ← y ← 2, r ← 1.
- Set y ← x. For j = 1, …, r: set x ← x2 + c mod n. Advance x by r steps from the saved y.
- Set k ← 0. While k < r:
- Accumulate q ← q · (y − x) mod n over a batch of steps, advancing x each time.
- Compute g ← gcd(q, n). If 1 < g < n, return g.
- If g = n, back up and test the batch one step at a time.
- Double r and return to step 2. If the search exceeds its budget, restart with a new c.
| Method | Evaluations per step | Memory | Notes |
|---|---|---|---|
| Floyd | 3 (one slow, two fast) | O(1) | Simple; the textbook version |
| Brent | 1 plus periodic saves | O(1) | Faster in practice; the usual choice |
| Distinguished points | 1 | O(1) per stored point | Used in parallel and distributed variants |
Section 03GCD batching
A GCD costs far more than a modular multiplication, so differences are accumulated into a product and a single GCD is taken per batch of 100 or so steps.
If the batch product becomes divisible by all of n — because two different primes collided within the same batch — the GCD returns n and the factor is lost. The remedy is to back up and replay the batch step by step. Implementations that omit this fallback fail on a small but real fraction of inputs.
Section 04Scope and variants
- What size is the expected factor?
- Under about 20 digits Pollard ρ — minimal setup, constant memory, ideal after trial division.
- 20 to 60 digits ECM — cost depends on the factor size, not on n.
- Balanced factors of a large n Quadratic sieve or NFS — cost depends on n.
Brent's improvement
Better cycle detection and batched GCDs; the standard implementation.
Rho for discrete logarithms
The same collision idea in a group, with the iteration tracking exponents so that a collision yields a linear relation and hence the logarithm.
Parallel rho
Distinguished points allow many machines to search independently with a linear speedup — the basis of distributed discrete logarithm records.
Rho degenerates on perfect powers, where the sequence modulo p and modulo n cycle together. Test for perfect powers first, and use trial division for very small n where the setup cost dominates.
ReferenceFrequently asked questions
Why avoid c = 0 and c = -2?
Because those choices make the iteration degenerate: the map has special structure that shortens the cycle drastically and destroys the birthday behaviour the analysis assumes. Any other small c works, and restarting with a new c is the standard response to failure.
Is the running time guaranteed?
No — it is an expected time based on a heuristic that the iteration behaves like a random map. The heuristic matches observation closely, but there is no proof, and individual runs can take considerably longer.
Why does rho fail on some inputs?
Either the budget is exhausted before a collision occurs, or a batched GCD returns n. Both are handled by restarting with a different c or by replaying a batch step by step, so failure is recoverable rather than terminal.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.