Faktorenzerlegung großer Zahlen

Schlagwörter:
Faktorenzerlegung à la Monte Carlo, Algorithmen, Referat, Hausaufgabe, Faktorenzerlegung großer Zahlen
Themengleiche Dokumente anzeigen

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit verschiedenen Algorithmen zur Faktorenzerlegung großer Zahlen. Im dritten Abschnitt wird die Methode von J. M. Pollard vorgestellt, die auf einer Monte-Carlo-Simulation basiert. Dabei wird untersucht, ob es einen größten gemeinsamen Teiler zwischen einer errechneten Zahl und der zu teilenden Zahl gibt, um den gesuchten Faktor zu finden. Das Dokument enthält auch ein Programmierbeispiel für diese Methode.

Im vierten Abschnitt werden weitere Algorithmen zur Faktorenzerlegung großer Zahlen vorgestellt. Einer davon ist der Algorithmus von J. M. Pollard, der darauf basiert, einen Teiler p zu finden, für den p-1 nur durch kleine Primfaktoren teilbar ist. Der SQUFOF-Algorithmus von D. Shanks wird auch erwähnt, der die Theorie der Ideale in quadratischen Zahlkörpern verwendet.

Das Dokument erklärt jeden Algorithmus im Detail und gibt auch Tipps, wie man diese Algorithmen optimieren kann. Das Programmierbeispiel für die Methode von J. M. Pollard ist auch nützlich für Leser, die selbst mit Faktorenzerlegung experimentieren möchten. Insgesamt ist das Dokument informativ und verständlich geschrieben, so dass auch Laien es verstehen können.
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

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