Kettenbruchmethode
Die Kettenbruchmethode (Abk.: CFRAC) berechnet zwei Teiler einer natürlichen Zahl, die keine Primzahl ist. Durch wiederholte Anwendung lässt sich so die Primfaktorzerlegung dieser Zahl ermitteln.
Die Kettenbruchmethode wurde 1931 von Derrick Henry Lehmer und dem Mathematik-Liebhaber Ralph Ernest Powers veröffentlicht, der auch durch zahlentheoretische Rechenergebnisse bekannt ist. Über Jahrzehnte hinweg wurde sie kaum verwendet, da sie auf den zur Verfügung stehenden Rechenmaschinen häufig nach mehreren Stunden noch keine Faktorisierung fand. Im Jahr 1970 programmierten Michael Morrison und John Brillhart die Kettenbruchmethode auf einem Großrechner und berechneten damit die Faktorisierung der siebten Fermat-Zahl. In den achtziger Jahren war die Kettenbruchmethode das Standardverfahren für die Faktorisierung großer Zahlen. Das waren damals Zahlen mit bis zu fünfzig Dezimalstellen. 1990 wurde mit dem quadratischen Sieb ein neuer Algorithmus vorgestellt, der die Nachfolge der Kettenbruchmethode antrat. Die Laufzeit der Kettenbruchmethode in O-Notation ist , wobei N die zu faktorisierende Zahl ist.
Funktionsweise
[Bearbeiten | Quelltext bearbeiten]Der Algorithmus sucht eine Kongruenz der Form x2 ≡ y2 (mod N). Um diese zu finden, multipliziert er geeignete Kongruenzen der Form x2 ≡ y (mod N). Solche Kongruenzen führen zu einer Faktorisierung von N (genauer beschrieben im Artikel Dixons Faktorisierungsmethode.)
Bei der Kettenbruchmethode nutzt man die Kettenbruchentwicklung von , um solche Kongruenzen zu finden. Die Kettenbruchentwicklung liefert beste Näherungen der Wurzel von N als Brüche der Form . Jede Näherung liefert eine Kongruenz x2 ≡ y (mod N) für x = p und y = x2 − q2 · N. Da der Bruch eine beste Näherung für ist, ist y klein und mit hoher Wahrscheinlichkeit glatt und man braucht nur wenige solcher Kongruenzen.
Algorithmus nach Morrison und Brillhart
[Bearbeiten | Quelltext bearbeiten]Die hier beschriebene Variante der Kettenbruchmethode entspricht derjenigen, die von Morrison und Brillhart in ihrem Aufsatz „A Method of Factoring and the Factorization of “ veröffentlicht wurde. Der Algorithmus besteht aus drei wesentlichen Schritten. Die zu faktorisierende Zahl wird im Weiteren mit bezeichnet.
Schritt A
[Bearbeiten | Quelltext bearbeiten]Wähle eine natürliche Zahl und berechne die Kettenbruchentwicklung von . Die Kettenbruchentwicklung kann an einer beliebigen Stelle abgebrochen werden, sodass man einen Kettenbruch der Form
erhält. Man berechnet nun die Paare , wobei der Zähler und der Nenner der -ten Konvergente sind und sich nach der Formel
berechnet.
Schritt B
[Bearbeiten | Quelltext bearbeiten]Aus den in Schritt A erzeugten -Paaren werden diejenigen ausgewählt, bei denen alle Primfaktoren von einer vorher festgelegten Faktorbasis entstammen. Die Faktorbasis enthält üblicherweise die Zahl −1 und alle Primzahlen, die Teiler von Q sein können, bis zu einer bestimmten Schranke. Man braucht nur die Primzahlen p mit oder in die Faktorbasis aufzunehmen, denn Q kann nur durch diese p teilbar sein.
Durch mehrfache Probedivision lässt sich feststellen, ob das jeweilige ein Produkt von Zahlen aus der Faktorbasis ist, und nebenbei erhält man die Primfaktorzerlegung von .
Mit den ausgewählten -Paaren füllt man eine Tabelle. Diese Tabelle enthält eine Spalte für jede Zahl der Faktorbasis. In die Faktorbasisspalten wird die Zahl 1 eingetragen, wenn der jeweilige Faktor in der Primzahlzerlegung von ungerade oft vorkommt. Andernfalls trägt man 0 ein. Der Tabelleneintrag für das Paar und die Faktorbasis sieht beispielsweise wie folgt aus:
−1 | 2 | 3 | 5 | 7 | 11 | 13 | |
---|---|---|---|---|---|---|---|
(375, −220) | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
Dann bestimmt man eine Auswahl von Tabellenzeilen, für die die Summe der Einträge in jeder Tabellenspalte gerade ist, sodass das Produkt der der ausgewählten Zeilen jeden Faktor mit einer geraden Potenz enthält und somit eine Quadratzahl ist. Das ist sicher dann möglich, wenn die Zahl der Tabellenzeilen mindestens um eins größer ist als die Zahl der Faktoren in der Faktorbasis und damit der Tabellenspalten.
Schritt C
[Bearbeiten | Quelltext bearbeiten]Man multipliziert die A aller Paare und die Q aller Paare der ausgewählten Tabellenzeilen. So erhält man die Legendre-Kongruenz
- .
Man berechnet dann und .
Wenn und , dann sind und echte Teiler von N. Anderenfalls kann eine andere Auswahl von Tabellenzeilen erfolgreich sein. Ggfs. muss man noch weitere Zeilen berechnen.
Geschichte
[Bearbeiten | Quelltext bearbeiten]Der erste Schritt auf dem Weg zur Kettenbruchmethode war die 1643 von Pierre de Fermat beschriebene Faktorisierungsmethode von Fermat. Dieses Rechenverfahren findet zwei Quadratzahlen und , sodass gilt. ist auch hier wieder die zu faktorisierende Zahl. Aufgrund der 3. Binomischen Formel gilt
und und sind deshalb Teiler von .
1798 veröffentlichte Adrien-Marie Legendre sein Buch „Essai sur la théorie des nombres“. In diesem findet sich mit den Legendre-Kongruenzen eine Weiterentwicklung der Methode von Fermat. Die Differenz der Quadratzahlen und muss nicht mehr gleich sein, sondern kann ein beliebiges Vielfaches von sein. Die Wurzeln und der Quadratzahlen müssen zudem drei Bedingungen erfüllen: , und . Unter diesen Voraussetzungen ist ein Teiler von und sowohl der größte gemeinsame Teiler als auch sind Faktoren von .
Literatur
[Bearbeiten | Quelltext bearbeiten]- Carl Pomerance: A Tale of Two Sieves. (PDF; 275 kB) In: Notices of the AMS. Bd. 43, Nr. 12, 1996, S. 1473–1485.
- D. H. Lehmer, R. E. Powers: On Factoring Large Numbers. In: Bulletin of the American Mathematical Society. Bd. 37, 1931, S. 770–776 (doi:10.1090/S0002-9904-1931-05271-X).
- Michael A. Morrison, John Brillhart: A Method of Factoring and the Factorization of . In: Mathematics of Computation. Bd. 29, Nr. 129, 1975, S. 183–205 (doi:10.2307/2005475).