Faktorenzerlegung großer Zahlen

Referat
Faktorenzerlegung großer Zahlen3.) Faktorenzerlegung à la Monte Carlo :Bei der Methode von J. M. Pollard ist es nicht immer möglich bei einer teilbaren Zahl einen Faktor zu finden. Die Suche wird zu einem Glücksspiel. Man untersucht ob es von einer natürlichen Zahl N und einer errechneten Zahl P einen größten gemeinsamen Teiler gibt. P bekommt man, indem zwei neue Variablen (x , y ) einführt, für welche gilt : f(x) x c (c 0;2 ) x x c ; y (y c) c P P1 ( y - x ) Als Startwert für x , y , und P wird 1 verwendet. 1.Schritt: Setze x 1 ;y 1 ;P 12.Schritt: Setze x x c ; y (y c) c und P P1 ( y - x )3.Schritt: Berechne den ggT von P und N. Fals das Ergebnis 1 ist , Wiederhole den Vorgang ab dem Schritt 2 . Bei allen anderen Ergebnissen hat man mit dem ggT den gesuchten Teiler gefunden . Achtung : ...