Algoritmeprincipe:
Pollard Rho is een probabilistisch algoritme voor het ontbinden van gehele getallen, vooral effectief voor het vinden van middelgrote factoren van samengestelde getallen. De naam van het algoritme komt van zijn traject dat lijkt op de Griekse letter ρ (rho).
Optimalisatiestrategieën:
- Proefdeling Optimalisatie:Gebruik eerst kleine priemgetallen (2, 3, 5, 7, 11...) voor proefdeling om snel kleine factoren te vinden.
- Pollard Rho:Voor grotere samengestelde getallen, gebruik de pseudo-willekeurige reeks x = (x² + c) mod n om factoren te vinden.
- Floyd's Cycle Detectie Algoritme:Gebruik snelle en langzame pointers om cycli in de reeks te detecteren, optimaliseert ruimtecomplexiteit.
- Miller-Rabin Priemtest:Na het vinden van een factor, controleer of deze priem is om verdere onnodige ontbinding te voorkomen.
- Recursieve Ontbinding:Ontbind de gevonden factoren recursief totdat alle factoren priem zijn.
Tijdcomplexiteit:
- Proefdeling:O(√n), geschikt voor kleine getallen of het snel vinden van kleine factoren.
- Pollard Rho:Verwachte tijd O(n^(1/4)), zeer efficiënt voor getallen met middelgrote factoren.
- Miller-Rabin:O(k log³n), waarbij k het aantal testronden is, gebruikt voor priemtesten.