Pollard Rho Algorithm
Pollard's rho uses a pseudorandom sequence x_{i+1}=f(x_i) mod n to find factors of large numbers, with expected complexity O(n^(1/4)).
Purpose
To factor medium-sized integers, used to attack weak RSA moduli.
Mechanism
Generate a sequence with f(x)=x^2+c mod n and find cycles with Floyd's algorithm. Along the cycle, gcd(|x_i-x_j|, n) may yield a non-trivial factor. The birthday paradox gives an expected O(p^(1/2)) steps, where p is the smallest prime factor.
Use cases
- Integer factorization
- RSA attacks
- Number-theoretic algorithms
Related tools
Prime Checker
Prime Checker — pure client-side tool. Privacy-first, no server round-trip. TOOL
Factor Calculator
Factor Calculator — pure client-side tool. Privacy-first, no server round-trip. TOOL
Pollard Rho Factorization
Pollard Rho Factorization — pure client-side tool. Privacy-first, no server round-trip. TOOL