imported>Claude J: /* Literatur */

2020-07-11T13:06:06Z

Literatur

Neue Seite

Die '''Kettenbruchmethode''' (Abk.: '''CFRAC''') berechnet zwei [[Teilbarkeit|Teiler]] einer [[Natürliche Zahl|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 [[Quadratisches Sieb|quadratischen Sieb]] ein neuer Algorithmus vorgestellt, der die Nachfolge der Kettenbruchmethode antrat. Die [[Laufzeit (Informatik)|Laufzeit]] der Kettenbruchmethode in [[Landau-Symbole|O-Notation]] ist <math>O\left(e^{\sqrt{2\log N \log\log N}}\right)</math>, wobei ''N'' die zu faktorisierende Zahl ist.

== Funktionsweise ==

Der Algorithmus sucht eine [[Kongruenz (Zahlentheorie)|Kongruenz]] der Form ''x''2 ≡ ''y''2 (mod ''N''). Um diese zu finden, multipliziert er geeignete Kongruenzen der Form ''x''2 ≡ ''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 <math>\sqrt{N}</math>, um solche Kongruenzen zu finden. Die Kettenbruchentwicklung liefert [[Kettenbruch#Beste Näherungen|beste Näherungen]] der Wurzel von ''N'' als Brüche der Form <math> \frac{p}{q} </math>. Jede Näherung liefert eine Kongruenz ''x''2 ≡ ''y'' (mod ''N'') für ''x'' = ''p'' und ''y'' = ''x''2 − ''q''2 · ''N.'' Da der Bruch eine beste Näherung für <math>\sqrt{N}</math> ist, ist ''y'' klein und mit hoher Wahrscheinlichkeit [[glatte Zahl|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 <math>F_7</math>“ veröffentlicht wurde. Der [[Algorithmus]] besteht aus drei wesentlichen Schritten. Die zu faktorisierende Zahl wird im Weiteren mit <math>N</math> bezeichnet.

=== Schritt A ===

Wähle eine natürliche Zahl <math>k \ge 1</math> und berechne die [[Kettenbruch]]entwicklung von <math>\sqrt{kN}</math>. Die Kettenbruchentwicklung kann an einer beliebigen Stelle <math>n-1</math> abgebrochen werden, sodass man einen Kettenbruch der Form
:<math>[ q_0; q_1, q_2, \ldots, q_{n-1}, \frac{\sqrt{kN} + P_n}{Q_n}]</math>
erhält. Man berechnet nun die Paare <math>(A_{i-1}, Q_i)</math>, wobei <math>A_{i}</math> der Zähler und <math>B_{i}</math> der Nenner der <math>i</math>-ten [[Kettenbruch#Endliche Kettenbrüche und ihre Näherungsbrüche|Konvergente]] sind und sich <math>Q_i</math> nach der Formel
:<math>Q_i = (-1)^i \cdot (A_{i-1}^2 - kNB_{i-1}^2)</math>
berechnet.

=== Schritt B ===

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

Durch mehrfache [[Probedivision]] lässt sich feststellen, ob das jeweilige <math>Q</math> ein Produkt von Zahlen aus der Faktorbasis ist, und nebenbei erhält man die Primfaktorzerlegung von <math>Q</math>.

Mit den ausgewählten <math>(A,Q)</math>-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 <math>Q</math> ungerade oft vorkommt. Andernfalls trägt man 0 ein. Der Tabelleneintrag für das Paar <math>(375, -220 = -1 \cdot 2^2 \cdot 5 \cdot 11)</math> und die Faktorbasis <math>\{-1,2,3,5,7,11,13\}</math> sieht beispielsweise wie folgt aus:
{| class="wikitable"
|- class="hintergrundfarbe5"
! !! −1 !! 2 !! 3 !! 5 !! 7 !! 11 !! 13
|-
| class="hintergrundfarbe5" | (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 <math>Q</math> 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]]
:<math>x^2 = \prod A^2 \equiv \prod Q = y^2\; ( \bmod \, N)</math>.
Man berechnet dann <math>d_1 = \operatorname{ggT}(x - y, N)</math> und <math>d_2 = \operatorname{ggT}(x + y, N)</math>.

Wenn <math>x \not\equiv y \; ( \bmod \, N)</math> und <math>x \not\equiv -y \; ( \bmod \, N)</math>, dann sind <math>d_1</math> und <math>d_2</math> 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 <math>x^2</math> und <math>y^2</math>, sodass <math>x^2 - y^2 = N</math> gilt. <math>N</math> ist auch hier wieder die zu faktorisierende Zahl. Aufgrund der [[Binomische Formeln|3. Binomischen Formel]] gilt
:<math>N = x^2 - y^2 = (x+y)(x-y)</math>
und <math>x + y</math> und <math>x - y</math> sind deshalb Teiler von <math>N</math>.

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

== Literatur ==

* [[Carl Pomerance]]: [http://www.ams.org/notices/199612/pomerance.pdf ''A Tale of Two Sieves.''] (PDF; 275 kB) In: ''Notices of the AMS.'' Bd. 43, Nr. 12, 1996, S. 1473–1485.
* [[Derrick Henry Lehmer|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 <math>F_7</math>.'' In: ''Mathematics of Computation.'' Bd. 29, Nr. 129, 1975, S. 183–205 ({{DOI|10.2307/2005475}}).

[[Kategorie:Faktorbasisverfahren]]

Kettenbruchmethode - Versionsgeschichte

imported>Claude J: /* Literatur */