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 ${\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}$, wobei N die zu faktorisierende Zahl ist.

Funktionsweise

Der Algorithmus sucht eine Kongruenz der Form x² ≡ y² (mod N). Um diese zu finden, multipliziert er geeignete Kongruenzen der Form x² ≡ 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 ${\displaystyle {\sqrt {N}}}$, um solche Kongruenzen zu finden. Die Kettenbruchentwicklung liefert beste Näherungen der Wurzel von N als Brüche der Form ${\displaystyle {\frac {p}{q}}}$. Jede Näherung liefert eine Kongruenz x² ≡ y (mod N) für x = p und y = x² − q² · N. Da der Bruch eine beste Näherung für ${\displaystyle {\sqrt {N}}}$ ist, ist y klein und mit hoher Wahrscheinlichkeit glatt und man braucht nur wenige solcher Kongruenzen.

Algorithmus nach Morrison und Brillhart

Die hier beschriebene Variante der Kettenbruchmethode entspricht derjenigen, die von Morrison und Brillhart in ihrem Aufsatz „A Method of Factoring and the Factorization of ${\displaystyle F_{7}}$“ veröffentlicht wurde. Der Algorithmus besteht aus drei wesentlichen Schritten. Die zu faktorisierende Zahl wird im Weiteren mit ${\displaystyle N}$ bezeichnet.

Schritt A

Wähle eine natürliche Zahl ${\displaystyle k\geq 1}$ und berechne die Kettenbruchentwicklung von ${\displaystyle {\sqrt {kN}}}$. Die Kettenbruchentwicklung kann an einer beliebigen Stelle ${\displaystyle n-1}$ abgebrochen werden, sodass man einen Kettenbruch der Form

${\displaystyle [q_{0};q_{1},q_{2},\ldots ,q_{n-1},{\frac {{\sqrt {kN}}+P_{n}}{Q_{n}}}]}$

erhält. Man berechnet nun die Paare ${\displaystyle (A_{i-1},Q_{i})}$, wobei ${\displaystyle A_{i}}$ der Zähler und ${\displaystyle B_{i}}$ der Nenner der ${\displaystyle i}$-ten Konvergente sind und sich ${\displaystyle Q_{i}}$ nach der Formel

${\displaystyle Q_{i}=(-1)^{i}\cdot (A_{i-1}^{2}-kNB_{i-1}^{2})}$

berechnet.

Schritt B

Aus den in Schritt A erzeugten ${\displaystyle (A,Q)}$-Paaren werden diejenigen ausgewählt, bei denen alle Primfaktoren von ${\displaystyle Q}$ 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 ${\displaystyle p=2}$ oder ${\displaystyle (kN)^{(p-1)/2}\,{\bmod {\;}}p\leq 1}$ in die Faktorbasis aufzunehmen, denn Q kann nur durch diese p teilbar sein.

Durch mehrfache Probedivision lässt sich feststellen, ob das jeweilige ${\displaystyle Q}$ ein Produkt von Zahlen aus der Faktorbasis ist, und nebenbei erhält man die Primfaktorzerlegung von ${\displaystyle Q}$.

Mit den ausgewählten ${\displaystyle (A,Q)}$-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 ${\displaystyle Q}$ ungerade oft vorkommt. Andernfalls trägt man 0 ein. Der Tabelleneintrag für das Paar ${\displaystyle (375,-220=-1\cdot 2^{2}\cdot 5\cdot 11)}$ und die Faktorbasis ${\displaystyle \{-1,2,3,5,7,11,13\}}$ sieht beispielsweise wie folgt aus:

Dann bestimmt man eine Auswahl von Tabellenzeilen, für die die Summe der Einträge in jeder Tabellenspalte gerade ist, sodass das Produkt der ${\displaystyle Q}$ 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

Man multipliziert die A aller Paare und die Q aller Paare der ausgewählten Tabellenzeilen. So erhält man die Legendre-Kongruenz

${\displaystyle x^{2}=\prod A^{2}\equiv \prod Q=y^{2}\;({\bmod {\,}}N)}$.

Man berechnet dann ${\displaystyle d_{1}=\operatorname {ggT} (x-y,N)}$ und ${\displaystyle d_{2}=\operatorname {ggT} (x+y,N)}$.

Wenn ${\displaystyle x\not \equiv y\;({\bmod {\,}}N)}$ und ${\displaystyle x\not \equiv -y\;({\bmod {\,}}N)}$, dann sind ${\displaystyle d_{1}}$ und ${\displaystyle d_{2}}$ echte Teiler von N. Anderenfalls kann eine andere Auswahl von Tabellenzeilen erfolgreich sein. Ggfs. muss man noch weitere Zeilen berechnen.

Geschichte

Der erste Schritt auf dem Weg zur Kettenbruchmethode war die 1643 von Pierre de Fermat beschriebene Faktorisierungsmethode von Fermat. Dieses Rechenverfahren findet zwei Quadratzahlen ${\displaystyle x^{2}}$ und ${\displaystyle y^{2}}$, sodass ${\displaystyle x^{2}-y^{2}=N}$ gilt. ${\displaystyle N}$ ist auch hier wieder die zu faktorisierende Zahl. Aufgrund der 3. Binomischen Formel gilt

${\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}$

und ${\displaystyle x+y}$ und ${\displaystyle x-y}$ sind deshalb Teiler von ${\displaystyle N}$.

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 ${\displaystyle x^{2}}$ und ${\displaystyle y^{2}}$ muss nicht mehr gleich ${\displaystyle N}$ sein, sondern kann ein beliebiges Vielfaches von ${\displaystyle N}$ sein. Die Wurzeln ${\displaystyle x}$ und ${\displaystyle y}$ der Quadratzahlen müssen zudem drei Bedingungen erfüllen: ${\displaystyle 0<x,y<N}$, ${\displaystyle x\neq y}$ und ${\displaystyle x+y\neq N}$. Unter diesen Voraussetzungen ist ${\displaystyle N}$ ein Teiler von ${\displaystyle x^{2}-y^{2}=(x+y)(x-y)}$ und sowohl der größte gemeinsame Teiler ${\displaystyle \operatorname {ggT} (N,x+y)}$ als auch ${\displaystyle \operatorname {ggT} (N,x-y)}$ sind Faktoren von ${\displaystyle N}$.

Literatur

• Michael A. Morrison, John Brillhart: A Method of Factoring and the Factorization of ${\displaystyle F_{7}}$. In: Mathematics of Computation. Bd. 29, Nr. 129, 1975, S. 183–205 (doi:10.2307/2005475).
• 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).
• Carl Pomerance: A Tale of Two Sieves. (PDF; 275 kB) In: Notices of the AMS. Bd. 43, Nr. 12, 1996, S. 1473–1485.