Faktorenzerlegung großßer Zahlen

Schlagwörter:
Faktorenzerlegung à la Monte Carlo, weitere Algorithmen, J. M. Pollard, SQUFOF-Algorithmus von D. Shanks, Referat, Hausaufgabe, Faktorenzerlegung großßer Zahlen
Themengleiche Dokumente anzeigen

Referat
Faktorenzerlegung großer Zahlen 3.) 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 1 2.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 . ...

Autor:
Anzahl Wörter:
603
Art:
Referat
Sprache:
Deutsch
Zurück