CFRAC

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 R. E. Powers veröffentlicht. Ü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 A. Morrison und John Brillhart die Kettenbruchmethode auf einem Großrechner und berechneten damit die Faktorisierung der siebten Fermat-Zahl. In den achtziger Jahren des zwanzigsten Jahrhunderts 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 $O\left(e^{\sqrt{2\log n \log\log n}}\right)$.

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 F₇“ veröffentlicht wurde. Der Algorithmus besteht aus drei wesentlichen Schritten. Die zu faktorisierende Zahl wird im Weiteren mit N bezeichnet.

Schritt A

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

$[ q_0; q_1, q_2, \ldots, q_{n-1}, \frac{\sqrt{kN} + P_n}{Q_n}]$

erhält. Man berechnet nun die Paare (A_{i − 1},Q_i), wobei A_{i − 1} der Zähler der (i − 1)-ten Konvergente ist und sich Q_i nach der Formel

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

berechnet.

Schritt B

Aus den in Schritt A erzeugten (A,Q)-Paaren werden diejenigen ausgewählt, bei denen alle Primfaktoren von Q einer vorher festgelegten Faktorbasis entstammen. Die Faktorbasis ist üblicherweise eine Menge, die die -1 und alle Primzahlen bis zu einer bestimmten Schranke enthält. Ein Beispiel ist die Menge $\{-1,2,3,5,\ldots, 97\}$. Durch mehrfache Probedivision lässt sich feststellen, ob das jeweilige Q ein Produkt von Zahlen aus der Faktorbasis ist und nebenbei erhält man die vollständige Primfaktorzerlegung von Q.

Mit den ausgewählten (A,Q)-Paaren füllt man eine Tabelle. Diese Tabelle enthält eine Spalte für jede Zahl der Faktorbasis. In die Faktorbasisspalten wird eine Eins eingetragen, wenn der jeweilige Faktor in der Primzahlzerlegung von Q ungerade oft vorkommt. Andernfalls trägt man eine Null ein. Der Tabelleneintrag für das Paar $(375, -220 = -1 \cdot 2 \cdot \cdot 5 \cdot 11)$ und die Faktorbasis { − 1,2,3,5,7,11,13} sieht beispielsweise wie folgt aus.

	-1	2	3	5	7	11	13
(375, -220)	1	0	0	1	0	1	0

Schritt C

Für jede der Teilmengen multipliziert man die As aller Paare und die Qs aller Paare. So erhält man die Legendre-Kongruenz

$\prod A^2 \equiv \prod Q \ \bmod N$

Berechne die Teiler $d_1 = \operatorname{ggT}(\prod A^2 - \prod Q, kN)$ und $d_2 = \operatorname{ggT}(\prod A^2 + \prod Q, N)$ von N.

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 x² und y², sodass x² − y² = N gilt. N ist auch hier wieder die zu faktorisierende Zahl. Aufgrund der 3. Binomischen Formel gilt

N = x² − y² = (x + y)(x − y)

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

Literatur

• Carl Pomerance: A Tale of Two Sieves. In: Notices of the AMS. Bd. 43, Nr. 12, 1996, S. 1473–1485
• Derrick Henry 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 F₇. In: Mathematics of Computation. Bd. 29, Nr. 129, 1975, S. 183–205 (doi:10.2307/2005475)