Hunting a factor
Trial division is slow for large composites. Pollard rho finds a factor far faster by generating a sequence that, viewed under an unknown prime factor, must eventually cycle. A collision in that hidden cycle reveals the factor.
The mechanism
- Generate values with a simple recurrence, often squaring and adding a constant under the full modulus.
- Track two walkers, one moving twice as fast as the other, so they meet inside any cycle.
- At each step take the greatest common divisor of their difference with the number.
When that divisor jumps above one but below the number, it is a genuine factor. The name comes from the rho shape of a path that runs into a loop.
Practical notes
If the walkers meet without yielding a factor, restart with a different constant. Combined with a primality test and recursion, Pollard rho factors large numbers that defeat trial division, and the cycle is reached after roughly the square root of the smallest factor in steps.
Key idea
Pollard rho walks a pseudo random sequence with two walkers and takes greatest common divisors of their gaps, exposing a hidden factor through a cycle far faster than trial division.