Principiul algoritmului:
Pollard Rho este un algoritm probabilistic pentru factorizarea numerelor întregi, eficient în special pentru găsirea factorilor de dimensiune medie ai numerelor compuse. Numele algoritmului provine de la traiectoria sa care seamănă cu litera grecească ρ (rho).
Strategii de optimizare:
- Optimizarea împărțirii prin încercare:Mai întâi, utilizați numere prime mici (2, 3, 5, 7, 11...) pentru împărțirea prin încercare pentru a găsi rapid factorii mici.
- Pollard Rho:Pentru numere compuse mai mari, utilizați secvența pseudoaleatoare x = (x² + c) mod n pentru a găsi factori.
- Algoritmul de detectare a ciclurilor Floyd:Utilizați pointeri rapizi și lenți pentru a detecta ciclurile în secvență, optimizând complexitatea spațiului.
- Testul de primalitate Miller-Rabin:După găsirea unui factor, verificați dacă este prim pentru a evita factorizări inutile suplimentare.
- Factorizare recursivă:Factorizați recursiv factorii găsiți până când toți sunt primi.
Complexitate temporală:
- Împărțire prin încercare:O(√n), potrivită pentru numere mici sau găsirea rapidă a factorilor mici.
- Pollard Rho:Timp estimat O(n^(1/4)), foarte eficient pentru numere cu factori de dimensiune medie.
- Miller-Rabin:O(k log³n), unde k este numărul de runde de testare, utilizat pentru testarea primalității.