Faktorenzerlegung großßer Zahlen

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit verschiedenen Algorithmen zur Faktorenzerlegung großer Zahlen. Ein wichtiger Aspekt ist die Methode von J. M. Pollard, bei der mittels eines Glücksspiels ein ggT von einer errechneten Zahl und der zu teilenden Zahl gefunden wird. Dabei kann man jedoch nicht immer einen Faktor entdecken. Des Weiteren wird darauf hingewiesen, dass bei Schritt 2 große Werte für Variablen entstehen können und die Ergebnisse daher mod N genommen werden müssen. Es wird auch ein Programmierbeispiel in Q-Basic angeführt. Im Dokument finden sich zudem Angaben zu einem weiteren Algorithmus von Pollard sowie zum SQUFOF-Algorithmus von D. Shanks. Der Artikel von Williams wird genannt als weitere Quelle für tiefergehende Infos zur Theorie der Ideale in quadratischen Zahlkörpern und zum Pollard-Algorithmus.
Direkt das Referat aufrufen

Auszug aus 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 . Achtung : Bei Schritt 2 entstehen für die Variablen x, y und P große Werte. Man muß daher die Ergebnisse modulo N nehmen . Fals N selbst der Teiler ist, gibt es zwei Möglichkeiten: N ist eine Primzahl Man kann die Konstante c verändern (z.B.:von 1 auf 2,3,...) Wenn einem die Berechnung des Schrittes 3 zu Zeitaufwendig ist, kann man dies umgehen, indem man erst nach z.B.: 10 -maliger Wiederholung des 2. Schrittes mit dem 3.Schritt beginnt .(Nur sehr seltener Verlust des Teilers ) . Hier ein Programmierbeispiel in Q-Basic : CLS:CLEAR: X 1: Y 1: P 1: T 1 Programm zur Faktorenzerlegung von MEISEL Marcus INPUT zu teilende Zahl (N): ;N : MO N: INPUT Konstante C: ; C: CLS X X C: GOSUB 9: Y (Y C) C: ...
Direkt das Referat aufrufen