Faktorisierungsmethode von Fermat

Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Mit seiner Hilfe kann man eine ungerade, zusammengesetze Zahl in zwei Faktoren zerlegen. Der Algorithmus berechnet also zu einer ungeraden, zusammengesetzten Zahl $n$ zwei ganze Zahlen $a$ und $b$, so dass gilt

$n=a\cdot b$

Verwendet man zusätzlich zur Faktorisierungsmethode von Fermat noch die Division durch 2, so kann durch wiederholte Anwendung die Primfaktorzerlegung einer Zahl bestimmt werden. Nahezu alle schnellen heute bekannten Faktorisierungsverfahren für große Zahlen gehen letztlich auf die Methode von Fermat zurück.

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

Funktionsweise

Für jede ungerade zusammengesetzte Zahl $n$ lässt sich mindestens eine Zerlegung in ein Produkt ungerader Zahlen größer als 1, $n=ab$, finden.

Dieses Produkt lässt mit den ganzen Zahlen $x=(a+b)/2$ und $y=(a-b)/2$ in der Form $n=(x+y)(x-y)$ schreiben (siehe 3. Binomischen Formel). Das Fermatsche Verfahren findet diejenige Zerlegung in zwei Faktoren $a$ und $b$ mit der geringsten Differenz von $a$ und $b$.

Das folgende Nassi-Shneiderman-Diagramm zeigt den Ablauf des Algorithmus. Dabei bezeichnet $\lceil {\sqrt {n}}\rceil$ die kleinste Zahl größer oder gleich ${\sqrt {n}}$.

Berechne $x=\lceil {\sqrt {n}}\rceil$
solange $x^{2}-n$ keine Quadratzahl
	$x\leftarrow x+1$
Berechne $y={\sqrt {x^{2}-n}}$
Berechne $a=x+y$
Berechne $b=x-y$

Anmerkungen

Der Algorithmus liefert auch korrekte Ergebnisse, wenn die vorgegebene Zahl eine Quadratzahl ist.

Eine Vereinfachung des Algorithmus erreicht man, indem man zwei Eigenschaften von Quadratzahlen ausnutzt, die auch schon Fermat bei seinen (von Hand durchgeführten) Berechnungen angewandt hat:

• $(x+1)^{2}$ lässt sich aus $x^{2}$ schnell berechnen:

  $(x+1)^{2}=x^{2}+2x+1$ (1. binomische Formel)

• es gibt nur 22 Möglichkeiten für die letzten beiden Ziffern einer Quadratzahl: 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.

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 $x$, für die man $x^{2}$ berechnet ist also die 42:

42² - 1729 = 35

43² - 1729 = 120

44² - 1729 = 207

45² - 1729 = 296

46² - 1729 = 387

47² - 1729 = 480

48² - 1729 = 575

49² - 1729 = 672

50² - 1729 = 771

51² - 1729 = 872

52² - 1729 = 975

53² - 1729 = 1080

54² - 1729 = 1187

55² - 1729 = 1296 fertig! 1296 = 36² und damit eine Quadratzahl.

Man erhält x=55 und y=36 und damit nach der 3. Binomischen Formel 1729 = 55²-36² = (55+36)(55-36) = 91 · 19. Die Probedivision durch die Primzahlen 2, 3, 5, 7, 11, 13, 17 und 19 wäre hier etwa doppelt so schnell zum Ziel gelangt. Wegen 1729 mod 4 = 1, hätte man sich allerdings den Test für die geraden Zahlen ersparen können. Da 120*480 bereits eine Quadratzahl ist, kann die Zerlegung mittels eines optimierten Verfahrens auch noch etwas schneller gefunden werden.

_{(Anmerkung: 91 = 7 · 13, die komplette Faktorisierung von 1729 ist somit 7 · 13 · 19 )}

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 $x$ ist somit 539. Es zeigt sich, dass $x^{2}-n$ schon beim ersten Einsetzen von $x$ ein Quadratzahl ist:

$x^{2}-n=539^{2}-290377=144=12^{2}$

Man kann nun sofort die beiden Faktoren von $n$ berechnen:

$y={\sqrt {x^{2}-n}}={\sqrt {144}}=12$

$a=x+y=539+12=551$

$b=x-y=539-12=527$

Eine Zerlegung von 290377 lautet damit

$290377=551\cdot 527$

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

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 $a=\left(1+\epsilon \right){\sqrt {n}}$ mit einem $\epsilon >0$ schreiben. Ist der Wert $\epsilon$ sehr viel kleiner als 1, ergibt sich für die Zahl der notwendigen Iterationen annähernd ${\frac {{\epsilon }^{2}}{2}}{\sqrt {n}}$. 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, nämlich bei n = 3p, wobei p eine Primzahl ist, benötigt dieses Verfahren O(n/6-√n)=O(n) viele Schritte.

Weiterentwicklung: Multiplikation mit einem Faktor

Um den hohen Rechenaufwand für Zahlen, die nicht in zwei annähernd gleich große Faktoren zerlegt werden können, zu umgehen kann man die Faktorisierungsmethode für ein Vielfaches $n'=k\cdot n$ der ursprünglichen Zahl $n$ durchführen. Dabei wird $k$ so gewählt, dass $n'$ in zwei annähernd gleich große Faktoren zerlegt werden kann. Eine günstige Wahl für $k$ sind ungerade Zahlen oder Produkte ungerader Zahlen. Die größten gemeinsamen Teiler zwischen $n$ und einem der berechneten Faktoren $a'$ und $b'$ von $n'$ sind jeweils Teiler von $n$:

$n=\operatorname {ggT} (n,a')\cdot {\frac {n}{\operatorname {ggT} (n,a')}}$

$n=\operatorname {ggT} (n,b')\cdot {\frac {n}{\operatorname {ggT} (n,b')}}$

Als Beispiel soll die Zahl 1729 in zwei Faktoren zerlegt werden. Die Zahl 120*1729 = 207480 kann bereits nach zwei Iterationen in die Faktoren 420 und 494 zerlegt werden. Teiler von 1729 können als größte gemeinsame Teiler berechnet werden:

$\operatorname {ggT} (1729,420)=7$

$\operatorname {ggT} (1729,494)=247$

Damit hat man eine Faktorisierungen der Zahl 1729:

$1729=7\cdot 247$

Literatur

• Donald E. Knuth: The Art of Computer Programming. Volume 2. Seminumerical Algorithms. Addison-Wesley, 1998, ISBN 0201896842

Weblinks

• Fermat's Factorization Method in MathWorld von Wolfram Research.
• The Prime Glossary: Fermat's method of factoring