Faktorenzerlegung großer Zahlen

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit der Faktorenzerlegung großer Zahlen. Es werden verschiedene Methoden und Algorithmen vorgestellt, um einen Teiler einer großen, teilbaren Zahl zu finden. Die Methode von J. M. Pollard wird detailliert beschrieben, die auf dem Glücksspielprinzip beruht und einen größten gemeinsamen Teiler von N und P sucht. Es wird auch darauf hingewiesen, dass bei großen Werten die Ergebnisse modulo N genommen werden müssen. Wenn Schritt 3 zu zeitaufwendig ist, kann man nach mehrfacher Wiederholung von Schritt 2 beginnen. Auch wird darauf hingewiesen, dass falls N selbst der Teiler ist, die Konstante c verändert werden kann. Es wird ein Programmierbeispiel in Q-Basic geliefert, um die Faktorenzerlegung zu verdeutlichen.

Weitere Algorithmen wie der von J. M. Pollard und der SQUFOF-Algorithmus von D. Shanks werden ebenfalls angesprochen. Letzterer erfordert Kenntnisse der Theorie der Ideale in quadratischen Zahlkörpern. Im Dokument wird auch erwähnt, dass ein Teiler einer Zahl gefunden ist, wenn p-1 nur durch kleine Primfaktoren teilbar ist. Auf diesen Rechengang wird in einem Artikel von Williams näher eingegangen.

Insgesamt handelt das Dokument von verschiedenen Methoden und Algorithmen, um einen Teiler von großen, teilbaren Zahlen zu finden. Es wird detailliert auf die Methode von J. M. Pollard eingegangen, inklusive Programmierbeispiel. Es werden weitere Algorithmen erwähnt und auch auf eine Theorie der Ideale in quadratischen Zahlkörpern hingewiesen, die für den SQUFOF-Algorithmus benötigt wird.
Direkt das Referat aufrufen

Auszug aus 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 : ...
Direkt das Referat aufrufen