Pollard-Rho-Methode

Die Pollard-Rho-Methoden sind Algorithmen zur Bestimmung der Periodenlänge einer Zahlenfolge, die mit einer mathematischen Funktion berechnet wird. Verschiedene schwierige mathematische Probleme wie der diskrete Logarithmus und die Faktorisierung lassen sich mit diesen Methoden berechnen. Eine optimierte Variante der Pollard-Rho-Methode wurde von John M. Pollard im Jahre 1975 zur Primfaktorzerlegung entwickelt. Derartige Verfahren lassen sich auch zur Berechnung von Kollisionen in Hash-Funktionen anwenden.

Bei den Pollard-Rho-Methoden werden Folgen von Teilergebnissen berechnet. Ab einem bestimmten Punkt wiederholt sich ein Teil dieser Teilergebnisse nur noch. Man kann die Teilergebnisse grafisch so anordnen, dass sich die Gestalt des Buchstaben ρ (Rho) erkennen lässt. Daraus leitet sich die Bezeichnung der Methoden ab.