Obwohl das Verfahren eines der langsamsten bekannten Verfahren ist, die dies bewerkstellen, so ist der Methode doch ein gewisser Stellenwert in der Mathematik einzuräumen, da nahezu alle schnellen heute bekannten Faktorisierungsverfahren auf die Methode von Fermat zurückgehen. Siehe auch Geschichte der Faktorisierungsverfahren.

Table of contents

1 Funktionsweise 2 Historisches 3 Laufzeitanalyse

Funktionsweise

Um ein natürliche Zahl n zu faktorisieren, berechnet man für x, beginnend bei die Zahlen Q(x):=x²-n. Sobald eine davon eine Quadratzahl ist, sagen wir x²-n=y², kann man eine Zerlegung von n angeben. Es ist nämlich nach der 3. Binomischen Formel n=x²-y²=(x-y)(x+y).

Die Suche kann man Beenden, wenn x den Wert (n+9)/6 übersteigt, da dann bereits sichergestellt ist, dass n eine Primzahl ist. Diese Abbruchbedingung gilt allerdings nur für ungerades n, was man aber voraussetzen können sollte.

Eine Beschleunigung des Verfahrens kann man erreichen, wenn man gewisse Restklassenbeziehungen ausnutzt. Etwa: Wenn n ≡ 1 (mod 4), und x ≡ 0 (mod 2), dann gilt Q(x) = x²-n ≡ 0-1 ≡ 3 (mod 4). Es gibt aber keine Quadratzahl, die kongruent 3 modulo 4 ist. Deshalb genügt es für n ≡ 1 (mod 4) die ungeraden Zahlen zu testen.

Historisches

1643 beschrieb Pierre de Fermat in einem Brief (vermutlich an Mersenne oder Frenicle) diese heute nach ihm benannte Faktorisierungsmethode. Einige Historiker vermuten, dass die Methode aber schon früher bekannt war.

Fermat nutzte bei der Berechnung (von Hand) aus, dass sich Q(x+1) aus Q(x) nach der folgenden Formel schnell berechnen lässt: Q(x+1) = Q(x)+2x+1. Weiterhin überprüfte Fermat nur die letzten beiden Ziffern von Q(x), da er die quadratischen Reste modulo 100 auswendig kannte und somit etwa 4/5 aller Zahlen garnicht mehr ganz auszurechnen brauchte.

Laufzeitanalyse