Pollard Rho Algorithm
Pollards Rho-Methode nutzt eine Pseudozufallsfolge x_{i+1}=f(x_i) mod n, um Faktoren großer Zahlen zu finden, mit erwarteter Komplexität O(n^(1/4)).
Zweck
Mittlere Ganzzahlen faktorisieren, genutzt für Angriffe auf schwache RSA-Moduli.
Mechanismus
Man erzeugt eine Folge mit f(x)=x^2+c mod n und findet Zyklen mit Floyds Algorithmus. Entlang des Zyklus kann ggT(|x_i-x_j|, n) einen nichttrivialen Faktor liefern. Das Geburtstagsparadoxon ergibt erwartete O(p^(1/2)) Schritte, wobei p der kleinste Primfaktor ist.
Anwendungsfälle
- Ganzzahlige Faktorisierung
- RSA-Angriffe
- Zahlentheoretische Algorithmen
Verwandte Tools
Primzahl-Prüfer
Prime Checker — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Teiler-Rechner
Factor Calculator — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Pollard-Rho-Faktorisierung
Pollard Rho Factorization — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG