Faktorisierungsmethode von Fermat - LinkFang.de





Faktorisierungsmethode von Fermat


Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl [math]n[/math] zwei Teiler [math]a[/math] und [math]b[/math], für die [math]a \cdot b = n[/math] gilt.

Die Faktorisierungsmethode von Fermat hat nur dann eine gute Laufzeit, wenn sich die zu zerlegende Zahl als Produkt annähernd gleich großer Faktoren darstellen lässt. Sie bildet zudem die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen, die in der Regel eine bessere Laufzeit aufweisen.

Pierre de Fermat beschrieb diese heute nach ihm benannte Faktorisierungsmethode 1643 in einem Brief, der vermutlich an Mersenne oder Frénicle de Bessy adressiert war. In diesem Brief demonstrierte er das Verfahren, indem er die Primfaktorzerlegung von 2.027.651.281 berechnete.[1] Einige Historiker vermuten, dass die Methode aber schon früher bekannt war.

Algorithmus

Sei [math]n[/math] (ungerade) die zu faktorisierende Zahl. Die Faktorisierungsmethode von Fermat berechnet nacheinander die Werte

[math]\left( \left\lceil \sqrt n \right\rceil \right)^2 - n[/math]
[math]\left( \left\lceil \sqrt n \right\rceil + 1 \right)^2 - n[/math]
[math]\left( \left\lceil \sqrt n\right \rceil + 2 \right)^2 - n[/math]
[math]\vdots[/math]

Dabei bezeichnet [math]\left\lceil \sqrt n \right\rceil[/math] die kleinste ganze Zahl größer oder gleich [math]\sqrt n[/math].

Dies wird fortgesetzt, bis einer dieser Werte eine Quadratzahl ist:

[math] \left( \left\lceil \sqrt n\right \rceil + z \right)^2 - n = x^2 - n = y^2 [/math].

Aufgrund der dritten Binomischen Formel gilt dann:

[math] n = x^2-y^2 = (x+y)(x-y) = a \cdot b [/math].

Dabei erhält man diejenige Zerlegung von [math]n[/math], für die das Verhältnis [math]a/b[/math] (mit [math] a \geq b[/math]) am kleinsten ist.

Das folgende Nassi-Shneiderman-Diagramm zeigt den Ablauf des Algorithmus, wie er schon von Fermat angewandt wurde. Dabei wird das wiederholte Quadrieren der obigen Beschreibung vermieden. Die einzelnen Werte werden dazu mittels der ersten binomischen Formel aus ihrem jeweiligen Vorgänger berechnet:

[math]\left( s + 1 \right)^2 - n = s^2 + 2s + 1 - n[/math]
Berechne [math]x = \left\lceil \sqrt n \right\rceil[/math]
Berechne [math]r = x^2 - n[/math]
solange [math]r[/math] keine Quadratzahl
[math]r \leftarrow r + 2x + 1[/math]
[math]x \leftarrow x + 1[/math]
Berechne [math]y = \sqrt{r}[/math]
Berechne [math]a = x + y[/math]
Berechne [math]b = x - y[/math]

Anmerkung

Indem man die letzten beiden Ziffern von [math]r[/math] überprüft, kann man in vielen Fällen ausschließen, dass [math]r[/math] eine Quadratzahl ist. Bei einer Quadratzahl gibt es nur 22 Möglichkeiten: 00, x1, x4, 25, y6 und x9, wobei x für eine gerade und y für eine ungerade Ziffer steht. Man kann also bei vielen Zahlen durch Überprüfung der letzten beiden Ziffern ausschließen, dass es Quadratzahlen sind. Auch Fermat nutzte diese Eigenschaft der Quadratzahlen.

Beispiele

Beispiel mit vielen Iterationen

Man möchte Faktoren der Zahl 1729 bestimmen. Die Wurzel aus 1729 beträgt etwa 41,6. Die erste Zahl [math]x[/math], für die man [math]r[/math] berechnet, ist also die 42.

[math]x[/math] [math]r = x^2 - n[/math] [math]2x + 1[/math]
42 35 85
43 120 87
44 207 89
45 296 91
46 387 93
47 480 95
48 575 97
49 672 99
50 771 101
51 872 103
52 975 105
53 1080 107
54 1187 109
55 1296 = 362

Man kann nun sofort die beiden Faktoren von [math]n[/math] berechnen:

[math]y = \sqrt{r} = 36[/math]
[math]a = x + y = 55 + 36 = 91[/math]
[math]b = x - y = 55 - 36 = 19[/math]

Eine Zerlegung von 1729 lautet damit

[math]1729 = 19 \cdot 91[/math]

Beispiel mit wenigen Iterationen

Am Beispiel der Zahl 290377 sieht man, dass es Zahlen gibt, bei der die Faktorisierungsmethode von Fermat sehr schnell eine Zerlegung berechnet. Die Wurzel aus 290377 beträgt etwa 538,9. Die nächste ganze Zahl [math]x[/math] ist somit 539. Es zeigt sich, dass [math]r[/math] schon im ersten Schritt eine Quadratzahl ist:

[math]r = x^2 - n = 539^2 - 290377 = 144 = 12^2[/math]

Man kann nun sofort die beiden Faktoren von [math]n[/math] berechnen:

[math]y = \sqrt{r} = \sqrt{144} = 12[/math]
[math]a = x + y = 539 + 12 = 551[/math]
[math]b = x - y = 539 - 12 = 527[/math]

Eine Zerlegung von 290377 lautet damit

[math]290377 = 551 \cdot 527[/math]

Weder [math]551 = 19 \cdot 29[/math] noch [math]527= 17 \cdot 31[/math] sind Primzahlen. Aber man kann den Algorithmus erneut auf 551 und 527 anwenden, um die vollständige Primfaktorzerlegung zu erhalten.

Funktionsweise

Die Faktorisierungsmethode von Fermat sucht nun nach zwei Quadratzahlen [math]x^2[/math] und [math]y^2[/math], die die Gleichung [math]x^2 - n = y^2[/math] erfüllen. Auf Grund der 3. Binomischen Formel ist dann

[math]n = x^2 - y^2 = (x+y)(x-y)[/math]

und [math]a = x + y[/math] und [math]b = x - y[/math] sind die gesuchten Teiler von [math]n[/math]. Das Fermatsche Verfahren findet dabei genau diejenige Teiler [math]a[/math] und [math]b[/math], die am nächsten zur Wurzel von [math]n[/math] liegen.

Es stellt sich die Frage, ob immer zwei Quadratzahlen [math]x^2[/math] und [math]y^2[/math] existieren, die obige Gleichung erfüllen. Wäre dies nicht der Fall, würde der Algorithmus in eine Endlosschleife geraten. Im Folgenden sei [math]n[/math] eine ungerade, zusammengesetzte Zahl, wie bei der Faktorisierungsmethode von Fermat vorausgesetzt. Dann ist [math]n[/math] das Produkt zweier ungerader Zahlen [math]a[/math] und [math]b[/math] und damit sind auch

[math]x = \frac{a+b}{2}[/math] und [math]y = \frac{a-b}{2}[/math]

ganze Zahlen. Durch eine einfache Rechnung unter Anwendung der Binomischen Formeln zeigt sich, dass [math]x^2 - y^2 = n[/math] ist:

[math]x^2 - y^2 = \left( \frac{a+b}{2} \right)^2 - \left( \frac{a-b}{2} \right)^2 = \frac{a^2 + 2ab + b^2}{4} - \frac{a^2 - 2ab + b^2}{4} = ab = n[/math]

Die Zahl [math]n[/math] lässt sich somit immer als Differenz zweier Quadratzahlen darstellen.

Laufzeitanalyse

Das Verfahren gelangt in wenigen Iterationen zu einer Lösung, wenn sich eine Zahl in zwei annähernd gleich große Faktoren zerlegen lässt. Wir können den größeren Faktor in der Form [math]a = \left(1 + \epsilon \right) \sqrt{n}[/math] mit einem [math]\epsilon \gt 0[/math] schreiben. Ist der Wert [math]\epsilon[/math] sehr viel kleiner als 1, ergibt sich für die Zahl der notwendigen Iterationen annähernd [math]\frac{{\epsilon}^{2}}{2} \sqrt{n}[/math]. In diesem Fall ist das Verfahren sehr viel schneller als die Probedivision.

Falls die Faktoren jedoch weit auseinanderliegen, braucht auch dieses Verfahren sehr viele Iterationen. Im schlechtesten Fall bei [math]n = 3p[/math], wobei [math]p[/math] eine Primzahl ist, benötigt dieses Verfahren [math]\Omega(n)[/math] viele Iterationen.

Erweiterung: Faktorisierung eines Vielfachen

Um die schlechte Laufzeit für Zahlen zu umgehen, die nicht das Produkt zweier annähernd gleich großer Faktoren sind, kann man die Faktorisierungsmethode für ein Vielfaches [math]n' = k \cdot n[/math] der ursprünglichen Zahl [math]n[/math] durchführen. Die größten gemeinsamen Teiler zwischen [math]n[/math] und je einem der berechneten Faktoren [math]a'[/math] und [math]b'[/math] von [math]n'[/math] liefern anschließend jeweils einen Teiler von [math]n[/math].

Als Beispiel betrachten wir die Zahl 1729, bei der die normale Faktorisierungsmethode 14 Schritte benötigt. Die Zahl [math]120 \cdot 1729 = 207480[/math] kann bereits nach zwei Iterationen in die Faktoren 420 und 494 zerlegt werden. Ein Teiler von 1729 kann als größter gemeinsamer Teiler berechnet werden:

[math]\operatorname{ggT}(1729,420) = 7[/math]

Mit [math]\frac{1729}{7} = 247[/math] hat man eine Faktorisierung der Zahl 1729:

[math]1729 = 7 \cdot 247[/math]

Es stellt sich nun das Problem, einen geeigneten Faktor [math]k[/math] zu finden. Russell Sherman Lehman hat 1974 mit der Faktorisierungsmethode von Lehman ein Verfahren entwickelt, das solche [math]k[/math] findet. Dadurch verkürzt sich die Laufzeit auf [math]O(n^\frac{1}{3} \log \log n)[/math].

Faktorisierungsmethode von Fermat als Primzahltest

Die Faktorisierungsmethode von Fermat kann als Primzahltest verwendet werden,[2] auch wenn dies nicht besonders effizient ist. Aus der Laufzeitanalyse ist bekannt, dass die ungünstigste Eingabe für den Algorithmus eine Zahl der Form [math]n = 3p[/math] ist ([math]p[/math] ist dabei eine Primzahl). In diesem Fall ist

[math]x = \frac{3 + p}{2} = \frac{3 + \tfrac n 3}{2} = \frac{9 + n}{6}[/math]

Lässt man nun als Eingabe [math]n[/math] des Algorithmus beliebige ungerade Zahlen zu und ist keine der Zahlen

[math]\left( \lceil \sqrt n \rceil \right)^2 - n, \left( \lceil \sqrt n \rceil + 1 \right)^2 - n, \ldots, \left( \frac{9+n}{6} \right)^2 - n[/math]

eine Quadratzahl, so ist [math]n[/math] eine Primzahl.

Literatur

Weblinks

Einzelnachweise

  1. Leonard E. Dickson: History of the Theory of Numbers. Volume 1. Divisibility and Primality. Dover Publications, 2005, ISBN 0-486-44232-2, S. 357
  2. Richard Crandall, Carl Pomerance: Prime Numbers. A Computational Perspective. 2. Auflage. Springer-Verlag, New York, 2005, ISBN 0-387-25282-7, S. 191–192

Kategorien: Faktorisierungsverfahren | Pierre de Fermat

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Faktorisierungsmethode von Fermat (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.