Benutzer:Lantani/Faktorisierungsmethode von Fermat

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

Neue Beispiele

Beispiel 1

$n=1729$
$x$	$2x+1$	$x^{2}$	$r=x^{2}-n$	$y={\sqrt {r}}$
42	85	1764	35	irrational
43	87	1849	120	irrational
44	89	1936	207	irrational
45	91	2025	296	irrational
46	93	2116	387	irrational
47	95	2209	480	irrational
48	97	2304	575	irrational
49	99	2401	672	irrational
50	101	2500	771	irrational
51	103	2601	872	irrational
52	105	2704	975	irrational
53	107	2809	1080	irrational
54	109	2916	1187	irrational
55	111	3025	1296	36

Beispiel 2

$n=2\,027\,651\,281$
$x$	$r=x^{2}-n$	mod	$y={\sqrt {r}}$	$x-y$
45030	49619	z9	> 222	< 44808
45031	139680	z	> 373	< 44658
45032	229743	z	> 479	< 44553
45033	319808	z9	> 565	< 44468
45034	409875	z9	> 640	< 44394
45035	499944	9	> 707	< 44328
45036	590015	z9	> 768	< 44268
45037	680088	z9	> 824	< 44213
45038	770163	z9	> 877	< 44161
45039	860240	z9	> 927	< 44112
45040	950319	z	> 974	< 44066
45041	1040400		1020	44021

Beispiel 3

$n=44\,021$
$x$	$r=x^{2}-n$	mod	$y={\sqrt {r}}$	$x-y$
210	79	z	> 8	< 202
211	500	9	> 22	< 189
212	923	z9	> 30	< 182
213	1348	z	> 36	< 177
214	1775	z9	> 42	< 172
215	2204	9	> 46	< 169
$\cdots$
224	6155	z9	> 78	< 146
225	6604	1.	> 81	< 144
255	21004	2.	> 144	< 111
261	24100	3.	> 155	< 106
285	37204	4.	> 192	< 93
315	55204	5.	> 234	< 81
339	70900	6.	> 266	< 73
345	75004	7.	> 273	< 72
375	96604	8.	> 310	< 65
405	120004	9.	> 346	< 59
411	124900	10.	> 353	< 58
$\cdots$
7335	53758204	333.	> 7331	< 4
7365	54199204	334.	> 7362	< 3
$\cdots$
22005	484176004	1017.	> 22003	< 2
22011	484440100	1018.	22010	1

Neuer Text

Der Fall, dass bereits $x=\left\lceil {\sqrt {n}}\right\rceil$ zu einer Quadratzahl $r=x^{2}-n$ führt, tritt ein, wenn $x-{\sqrt {n}}<1$. Dabei sind diese drei Bedingungen äquivalent:

• $x-{\sqrt {n}}<1$
• $r<2x-1$
• ${\sqrt {x+y}}-{\sqrt {x-y}}<{\sqrt {2}}$ mit $y={\sqrt {r}}$

Dieser Fall tritt also genau dann ein, wenn die Quadratwurzeln der beiden Faktoren einen Abstand kleiner als ${\sqrt {2}}$ haben.

Beweis:

Es sei $n\geqq 3$ ganz und ungerade. Wir definieren $x=\left\lceil {\sqrt {n}}\right\rceil$, $r=x^{2}-n$ und $y={\sqrt {r}}$. Damit sind $x$ und $r$ beide ganz und es gilt $x\geqq {\sqrt {n}}>1$ und $r\geqq 0$. Dagegen ist $y$ nicht notwendig ganz.

$x-{\sqrt {n}}=\left\lceil {\sqrt {n}}\right\rceil -{\sqrt {n}}<1$   nach der Definition der Aufrundungsklammer $\lceil \dots \rceil$

$x-1<{\sqrt {n}}={\sqrt {x^{2}-r}}$   durch einfache algebraische Umformungen

Da alle $x-1$ und ${\sqrt {x^{2}-r}}$ beide positiv sind, ist das äquivalent zu

$x^{2}-2x+1<x^{2}-r$

$r<2x-1$

$y={\sqrt {r}}<{\sqrt {2x-1}}$

$x>{\tfrac {1}{2}}(r+1)={\tfrac {1}{2}}(y^{2}+1)$

$x\pm y>{\tfrac {1}{2}}(y^{2}+1)\pm y={\tfrac {1}{2}}(y^{2}\pm 2y+1)={\tfrac {1}{2}}(y\pm 1)^{2}$

Für $z$ im Intervall $0\leqq z<x$ wird die Funktion $f(z)={\sqrt {x+z}}-{\sqrt {x-z}}$ definiert. Sie ist streng monoton steigend. Mit der Monotonie von $f$ folgt, dass $y<{\sqrt {2x-1}}\$ genau dann gilt, wenn $\ 0\leqq f(y)<f({\sqrt {2x-1}})$, und dies genau dann wenn $f^{2}(y)<f^{2}({\sqrt {2x-1}})$. Die beiden Seiten der Ungleichung werden jetzt einzeln berechnet:

$f^{2}(y)=({\sqrt {x+y}}-{\sqrt {x-y}})^{2}=(x+y)-2{\sqrt {(x+y)(x-y)}}+(x-y)=2x-2{\sqrt {x^{2}-y^{2}}}$

$f^{2}({\sqrt {2x-1}})=$

$x>(y^{2}+1)/2$

${\displaystyle }$

Algorithmus

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

$\left(\left\lceil {\sqrt {n}}\right\rceil \right)^{2}-n$

$\left(\left\lceil {\sqrt {n}}\right\rceil +1\right)^{2}-n$

$\left(\left\lceil {\sqrt {n}}\right\rceil +2\right)^{2}-n$

$\vdots$

Dabei bezeichnet $\left\lceil {\sqrt {n}}\right\rceil$ die kleinste ganze Zahl größer oder gleich ${\sqrt {n}}$.

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

$\left(\left\lceil {\sqrt {n}}\right\rceil +z\right)^{2}-n=x^{2}-n=y^{2}$

Aufgrund der dritten binomischen Formel gilt dann

$n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b.$

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

$\left(s+1\right)^{2}-n=s^{2}+2s+1-n$

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

Anmerkung

Indem man die letzten beiden Ziffern von $r$ überprüft, kann man in vielen Fällen ausschließen, dass $r$ 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:

$x^{2}=y^{2}+n{\bmod {q}}$

Wegen der Eigenschaft $(-x)^{2}=x^{2}$ kann es für $x$ maximal $(q+1)/2$ mögliche Reste geben, wenn $n$ und $q$ teilerfremd sind. Durch Kombinieren der Restklassen bezüglich verschiedener Primzahlen (bzw. kleiner Primzalpotenzen) lassen sich die Lösungen für $x$ pro verwendeter Restklasse jeweils nahezu halbieren.

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 $r$ berechnet, ist also die 42.

$x$	$r=x^{2}-n$	$2x+1$
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 $n$ berechnen:

$y={\sqrt {r}}=36$

$a=x+y=55+36=91$

$b=x-y=55-36=19$

Eine Zerlegung von 1729 lautet damit:

$1729=19\cdot 91$

19 ist Primzahl, 91 nicht. Man kann nun den Algorithmus erneut auf 19 und 91 anwenden, um die vollständige Primfaktorzerlegung zu erhalten.

Beispiel mit wenigen Iterationen

Am Beispiel der Zahl 717583 sieht man, dass es Zahlen gibt, bei der die Faktorisierungsmethode von Fermat sehr schnell eine Zerlegung berechnet. Die Wurzel aus 717583 beträgt etwa 847,1. Die nächste ganze Zahl $x$ ist somit 848. Es zeigt sich, dass $r$ schon im ersten Schritt eine Quadratzahl ist:

$r=x^{2}-n=848^{2}-717583=1521=39^{2}$

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

$y={\sqrt {r}}={\sqrt {1521}}=39$

$a=x+y=848+39=887$

$b=x-y=848-39=809$

Eine Zerlegung von 717583 lautet damit

$717583=809\cdot 887$

Hier sind 809 und 887 beide Primzahlen. Um das zu sehen und so die Vollständigkeit der Primfaktorzerlegung nachzuweisen, kann man den Algorithmus erneut auf 809 und 887 anwenden.

Grafisches Beispiel

Alle ganzzahligen Teiler können als Punkte in einer Teilerfläche dargestellt werden. Die $x$-Achse gibt jeweils die Teilerwerte wieder, die $y$-Achse entspricht einem ganzzahligen Zahlenstrahl (zur besseren Nachvollziehbarkeit werden im Beispiel die $x$- und $y$-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 $y=-x^{2}+px$ 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 $p$ der gemeinsamen negativen Parabel.

Beispiel:

$145=1\cdot 145=5\cdot 29$

Fermat's factorization in the divisor plane

Die komplementären Teilerpaare von $145$ sind die trivialen Teiler $1\cdot 145$ und die nicht-trivialen Teiler $5\cdot 29$.

Die Schnittpunkte von Parabeln der Form $y=-x^{2}+px$ mit der Parallelen zur $x$-Achse $y=145$ 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 $145$ wird $y=-x^{2}+25x$ identifiziert ($p=\lceil ({\sqrt {1}}45)\cdot 2\rceil =25$). Nach mehrfachem Verschieben werden die Teiler $5$ und $29$ mit der Parabel $y=-x^{2}+(5+29)x=-x^{2}+34x$ gefunden. Scheitelpunkt dieser Parabel ist $S(17,289)$.

Die Zahl $145$ ist somit als Differenz der Quadrate $17^{2}-(17-5)^{2}=17^{2}-12^{2}=289-144$ darstellbar. Die nicht-trivialen Teiler lassen sich über $17-12=5$ und $17+12=29$ berechnen.

Da Parabeln der Form $y=-x^{2}+(2p+1)x$ ausschließlich komplementäre Teiler zu geraden Zahlen liefern werden sie in Fermat's Methode nicht berücksichtigt.

Funktionsweise

Die Faktorisierungsmethode von Fermat sucht nach zwei Quadratzahlen $x^{2}$ und $y^{2}$, die die Gleichung $x^{2}-n=y^{2}$ erfüllen. Auf Grund der 3. binomischen Formel ist dann

$n=x^{2}-y^{2}=(x+y)(x-y)$

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

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

$x={\frac {a+b}{2}}$ und $y={\frac {a-b}{2}}$

ganze Zahlen. Durch eine einfache Rechnung unter Anwendung der binomischen Formeln zeigt sich, dass $x^{2}-y^{2}=n$ ist:

$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$

Die Zahl $n$ 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 $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 auseinander liegen, braucht auch dieses Verfahren sehr viele Iterationen. Im schlechtesten Fall bei $n=3p$, wobei $p$ eine Primzahl ist, benötigt dieses Verfahren $\Omega (n)$ 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 $n'=k\cdot n$ der ursprünglichen Zahl $n$ durchführen. Die größten gemeinsamen Teiler zwischen $n$ und je einem der berechneten Faktoren $a'$ und $b'$ von $n'$ liefern anschließend jeweils einen Teiler von $n$.

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

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

Mit ${\frac {1729}{7}}=247$ hat man eine Faktorisierung der Zahl 1729:

$1729=7\cdot 247$

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

Faktorisierungsmethode von Fermat als Primzahltest

Die Faktorisierungsmethode von Fermat kann als Primzahltest verwendet werden, 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 $n=3p$ ist ($p$ ist dabei eine Primzahl). In diesem Fall ist

$x={\frac {3+p}{2}}={\frac {3+{\tfrac {n}{3}}}{2}}={\frac {9+n}{6}}$

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

$\left(\lceil {\sqrt {n}}\rceil \right)^{2}-n,\left(\lceil {\sqrt {n}}\rceil +1\right)^{2}-n,\dotsc ,\left({\frac {9+n}{6}}\right)^{2}-n$

eine Quadratzahl, so ist $n$ eine Primzahl.

Literatur

• Hans Riesel: Prime Numbers and Computer Methods for Factorization. 2. Auflage. Birkhäuser, Boston 1994, ISBN 0-8176-3743-5.
• Donald E. Knuth: The Art of Computer Programming. Volume 2. Seminumerical Algorithms. 3. Auflage. Addison-Wesley, 1998, ISBN 0-201-89684-2.

Weblinks

• Eric W. Weisstein: Fermat’s Factorization Method. In: MathWorld (englisch).
• The Prime Glossary: Fermat’s method of factoring.
• Bruno Lehnen (GeoGebra-Materialien): Fermat's factorization in the divisor plane.