Faktorenzerlegung großer Zahlen

Schlagwörter:
Faktorenzerlegung à la Monte Carlo, Algorithmen, 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 . 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: ...

Autor:
Kategorie:
Sonstiges
Anzahl Wörter:
620
Art:
Referat
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bislang noch nicht bewertet.
Zurück