Algorithmus-Prinzip:
Pollard Rho ist ein probabilistischer Algorithmus zur ganzzahligen Faktorisierung, der besonders effektiv bei der Suche nach mittelgroßen Faktoren zusammengesetzter Zahlen ist.
Optimierungsstrategien:
- Probedivision-Optimierung:Zuerst kleine Primzahlen (2, 3, 5, 7, 11...) für die Probedivision verwenden, um schnell kleine Faktoren zu finden.
- Pollard Rho:Für größere zusammengesetzte Zahlen die pseudozufällige Sequenz x = (x² + c) mod n verwenden, um Faktoren zu finden.
- Floyds Zykluserkennung:Schnelle und langsame Zeiger verwenden, um Zyklen in der Sequenz zu erkennen.
- Miller-Rabin-Primzahltest:Nach dem Finden eines Faktors überprüfen, ob es sich um eine Primzahl handelt.
- Rekursive Faktorisierung:Gefundene Faktoren rekursiv faktorisieren, bis alle Primzahlen sind.
Zeitkomplexität:
- Probedivision:O(√n), geeignet für kleine Zahlen oder schnelles Auffinden kleiner Faktoren.
- Pollard Rho:Erwartete Zeit O(n^(1/4)), hocheffizient für Zahlen mit mittelgroßen Faktoren.
- Miller-Rabin:O(k log³n), wobei k die Anzahl der Testrunden ist.