A probabilistic heuristic integer factorization algorithm that uses a pseudorandom sequence in Z/nZ together with cycle detection and gcd computations to find a nontrivial factor.

Principle

Generate a sequence x_{i+1} = f(x_i) mod n for a polynomial f (commonly x^2 + c), detect a collision or short cycle in the sequence, and compute gcd(|x_i - x_j|, n) to extract a factor; randomness and the birthday paradox make collisions likely in sublinear time for small factors.

Demonstration

Choose f(x)=x^2+1 mod 8051, start x_0=2 and use Floyd's cycle detection; when two iterates become congruent modulo a nontrivial factor, gcd of their difference with 8051 yields a factor.

Misapplication

Relying on Pollard Rho as a guaranteed fast method for numbers whose smallest factor is very large, or failing to restart with different polynomials after long runs; poor choices cause long cycles and unproductive runs.

Consequence

Often finds relatively small factors quickly with little memory; effective as a middle-ground method after removing tiny factors by trial division and before heavier sieving methods.

Reversal

Replace pseudorandom iteration and cycle detection by structured relation collection across many values (as in quadratic or number-field sieves) to target large composite structure rather than single small factors.

Boundary

Heuristic and probabilistic: performance degrades when all prime factors are large or when the pseudorandom map exhibits pathological cycles; it does not replace algebraic sieves for very large semiprimes.

Semantic Tension

Sits between simple brute-force methods and large-scale sieves: faster than trial division for moderate factors but conceptually and practically different from deterministic algebraic algorithms like NFS or ECM.

Synthesis

Pollard Rho uses inexpensive modular iteration plus cycle detection and gcds to convert random collisions in a pseudorandom sequence into nontrivial factors, making it a lightweight probabilistic tool for finding small-to-moderate factors.