Faktorisierungsmethode von Fermat

Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl zwei Teiler und , für die 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 aber, dass die Methode schon früher bekannt war.

Algorithmus

Bearbeiten

Sei   die zu faktorisierende ungerade Zahl. Die Faktorisierungsmethode von Fermat berechnet nacheinander die Werte

 
 
 
 

Dabei bezeichnet   die kleinste ganze Zahl größer oder gleich  .

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

 

Aufgrund der dritten binomischen Formel gilt dann

 

Dabei erhält man diejenige Zerlegung von  , für die das Verhältnis   (mit  ) 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:

 
Berechne  
Berechne  
solange   keine Quadratzahl
 
 
Berechne  
Berechne  
Berechne  

Anmerkung

Bearbeiten

Indem man die letzten beiden Ziffern von   überprüft, kann man in vielen Fällen ausschließen, dass   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. Dies funktioniert auch mit anderen quadratischen Resten, etwa Zweierpotenzen, die sich auf einer klassischen Computerarchitektur leicht überprüfen lassen. Diese Idee kann man verallgemeinern, indem man nicht nur die Quadrate, sondern die quadratische Gleichung in zwei Variablen bezüglich ihrer Reste untersucht:

 

Wegen der Eigenschaft   kann es für   maximal   mögliche Reste geben, wenn   und   teilerfremd sind. Durch Kombinieren der Restklassen bezüglich verschiedener Primzahlen (bzw. kleiner Primzalpotenzen) lassen sich die Lösungen für   pro verwendeter Restklasse jeweils nahezu halbieren.

Beispiele

Bearbeiten

Beispiel mit vielen Iterationen

Bearbeiten

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

     
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   berechnen:

 
 
 

Eine Zerlegung von 1729 lautet damit:

 

Beispiel mit wenigen Iterationen

Bearbeiten

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   ist somit 539. Es zeigt sich, dass   schon im ersten Schritt eine Quadratzahl ist:

 

Man kann nun sofort die beiden Faktoren von   berechnen:

 
 
 

Eine Zerlegung von 290377 lautet damit

 

Weder   noch   sind Primzahlen. Aber man kann den Algorithmus erneut auf 551 und 527 anwenden, um die vollständige Primfaktorzerlegung zu erhalten.

Grafisches Beispiel

Bearbeiten

Alle ganzzahligen Teiler können als Punkte in einer Teilerfläche dargestellt werden. Die  -Achse gibt jeweils die Teilerwerte wieder, die  -Achse entspricht einem ganzzahligen Zahlenstrahl (zur besseren Nachvollziehbarkeit werden im Beispiel die  - und  -Achse im Verhältnis 1 zu 16 skaliert).

Die Teilerpunkte in einer Teilerfläche besitzen u. a. folgende Eigenschaften:

  • Alle Teilerpunkte der Teilerfläche können einer negativen Parabel der Form   zugeordnet werden.
  • Alle komplementären Teilerpaare einer Zahl befinden sich auf einer gemeinsamen Parabel.
  • Die Addition zweier komplementärer Teiler einer Zahl liefert den Koeffizienten   der gemeinsamen negativen Parabel.

Beispiel:

 
 
Fermat's factorization in the divisor plane

Die komplementären Teilerpaare von   sind die trivialen Teiler   und die nicht-trivialen Teiler  .

Die Schnittpunkte von Parabeln der Form   mit der Parallelen zur  -Achse   liefern somit Teilerkandidaten. Das Verschieben der Parabel liefert entweder die nicht-trivialen oder, im allerletzten Schritt, die trivialen Teiler einer Zahl.

Als erste negative Parabel mit einem Scheitelpunktwert größer   wird   identifiziert ( ). Nach mehrfachem Verschieben werden die Teiler   und   mit der Parabel   gefunden. Scheitelpunkt dieser Parabel ist  .

Die Zahl   ist somit als Differenz der Quadrate   darstellbar. Die nicht-trivialen Teiler lassen sich über   und   berechnen.

Da Parabeln der Form   ausschließlich komplementäre Teiler zu geraden Zahlen liefern werden sie in Fermat's Methode nicht berücksichtigt.

Funktionsweise

Bearbeiten

Die Faktorisierungsmethode von Fermat sucht nach zwei Quadratzahlen   und  , die die Gleichung   erfüllen. Auf Grund der 3. binomischen Formel ist dann

 

und   und   sind die gesuchten Teiler von  . Das Fermatsche Verfahren findet dabei genau diejenige Teiler   und  , die am nächsten zur Wurzel von   liegen.

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

  und  

ganze Zahlen. Durch eine einfache Rechnung unter Anwendung der binomischen Formeln zeigt sich, dass   ist:

 

Die Zahl   lässt sich somit immer als Differenz zweier Quadratzahlen darstellen.

Laufzeitanalyse

Bearbeiten

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   mit einem   schreiben. Ist der Wert   sehr viel kleiner als 1, ergibt sich für die Zahl der notwendigen Iterationen annähernd  . In diesem Fall ist das Verfahren sehr viel schneller als die Probedivision.

Falls die Faktoren jedoch weit auseinander liegen, braucht auch dieses Verfahren sehr viele Iterationen. Im schlechtesten Fall bei  , wobei   eine Primzahl ist, benötigt dieses Verfahren   viele Iterationen.

Erweiterung: Faktorisierung eines Vielfachen

Bearbeiten

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   der ursprünglichen Zahl   durchführen. Die größten gemeinsamen Teiler zwischen   und je einem der berechneten Faktoren   und   von   liefern anschließend jeweils einen Teiler von  .

Als Beispiel betrachten wir die Zahl 1729, bei der die normale Faktorisierungsmethode 14 Schritte benötigt. Die Zahl   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:

 

Mit   hat man eine Faktorisierung der Zahl 1729:

 

Es stellt sich nun das Problem, einen geeigneten Faktor   zu finden. Russell Sherman Lehman hat 1974 mit der Faktorisierungsmethode von Lehman ein Verfahren entwickelt, das solche   findet. Dadurch verkürzt sich die Laufzeit auf  .

Faktorisierungsmethode von Fermat als Primzahltest

Bearbeiten

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   ist (  ist dabei eine Primzahl). In diesem Fall ist

 

Lässt man nun als Eingabe   des Algorithmus beliebige ungerade Zahlen zu und ist keine der Zahlen

 

eine Quadratzahl, so ist   eine Primzahl.

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  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.