Diskussion:Kettenbruchmethode
aus Wikipedia, der freien Enzyklopädie
Der erste und der letzte Absatz sind spitze so, aber der zweite (i. e. der relevante) ist völlig unverständlich. Wie genau sieht denn die Methode aus? --Scherben 20:54, 11. Okt 2005 (CEST)
Ich habe einen Quelle gefunden, wo die Methode beschrieben ist. http://christianroepke.de/studium/krypto2/Seminararbeit-Kettenbrueche.pdf
Vielleicht schreibt ja jemand eine Zusammenfassung für Wikipedia.
Ich habe gerade festgestellt, dass unter dem angegebenen Link nichts mehr zu finden ist. Der Beitrag wurde wohl entfernt. Offenbar handelt es sich bei der Kettenbruchmethode im Prinzip auch um eine Variante der bereits 1926 von Maurice Kraitchik vorgeschlagenen Methode zur Faktorisierung, d.h. der Bestimmung der Primfaktorzerlegung großer ganzer Zahlen.
[Bearbeiten] Das Prinzip
Zur Faktorisierung der Zahl n werden Zahlen x,y gesucht, so dass n Teiler von x2 − y2 ist, da damit eine Faktorisierung der Form
angegeben werden kann, die in 50 % der Fälle echte Teiler von n als ggT(x+y,n) und ggT(x-y,n) liefern. Quadiert man verschiedene Zahlen und bildet den Rest der Division durch n, kann häufig durch geeignete Auswahl dieser Zahlen eine Quadratzahl gefunden werden, die das Produkt der Reste ist. Damit sind Zahlen mit der gesuchten Eigenschaft gefunden. Eine geeigente Auswahl kann mit Methoden der linearen Algebra aus der Primfaktorenzerlegung der Reste bestimmt werden.
Offenbar arbeiten praktisch alle Verfahren, die zur Faktorisierung großer Zahlen - 100 Stellen und mehr - nach diesem Grundprinzip.
