Αρχή Αλγορίθμου:
Pollard Rho is a probabilistic algorithm for integer factorization, especially effective at finding medium-sized factors of composite numbers. The algorithm's name comes from its trajectory resembling the Greek letter ρ (rho).
Optimization Strategies:
- Trial Division Optimization:First, use small primes (2, 3, 5, 7, 11...) for trial division to quickly find small factors.
- Pollard Rho:For larger composite numbers, use the pseudorandom sequence x = (x² + c) mod n to find factors.
- Floyd's Cycle Detection Algorithm:Use fast and slow pointers to detect cycles in the sequence, optimizing space complexity.
- Miller-Rabin Primality Test:After finding a factor, check if it is prime to avoid further unnecessary factorization.
- Recursive Factorization:Recursively factor the found factors until all are prime.
Χρονική Πολυπλοκότητα:
- Trial Division:O(√n), suitable for small numbers or quickly finding small factors.
- Pollard Rho:Expected time O(n^(1/4)), highly efficient for numbers with medium-sized factors.
- Miller-Rabin:O(k log³n), where k is the number of test rounds, used for primality testing.