A collision that finds a factor
A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.
