Pollard's rho: factor n by iterating x←x²+c (mod n) with two pointers (Floyd's cycle detection). When |x_slow−x_fast| shares a factor with n, we've found a divisor! Expected O(n^{1/4}) — much faster than trial division's O(n^{1/2}).
How to Use
Enter a composite number:
- Factor: A nontrivial divisor
- Trace: Iteration steps
- Full: Complete factorization
Birthday Paradox
Why O(n^{1/4})? If p|n, the sequence mod p has ~p values. By birthday paradox, collision after ~√p steps. Since p≤√n, we need ~n^{1/4} steps. The 'rho' name comes from the shape of the iteration trajectory (ρ).
Variants
- Brent's improvement: faster cycle detection
- Multiple polynomials: retry with different c
- GCD batching: accumulate products, GCD less often
Step-by-Step Instructions
- 1Enter composite n.
- 2Run iterations.
- 3Detect cycle.
- 4Find factor.
- 5Repeat for cofactor.