Diskussion:Faktorisierungsmethode von Fermat

Gerade und ungerade Zahlen

Das Verfahren von Fermat führt nur bei ungeraden zusammengesetzten Zahlen immer zum Erfolg. Es muss nämliche eine Zerlegung in zwei gerade oder zwei ungerade Faktoren geben.

Der Fall gerader Zahlen ist aber im Grunde irrelevant, weil immer zuvor Faktoren 2 abgespalten werden können. Ich denke es ist daher sinnvoll sich auf den Fall ungerader Zahlen zu beschränken.

Die Methode lässt sich jedoch auf gerade Zahlen anwenden, sofern diese auch durch 4 teilbar sind. Franz Scheerer 12.04.06

Einleitung

In der Einleitung stand der Satz

... die unabhängig von der Anzahl und Größe ihrer Primfaktoren effizient sind.

Diesen habe ich durch folgenden ersetzt

... die unabhängig von der Größe der berechneten Faktoren effizienter sind.

Ich halte es für sinnvoll hier auf die ermittelten Faktoren einzugehen, da damit der Bezug zum vorhergehenden Satz leichter ersichtlich ist. Das steht nicht im Widerspruch zum ursprünglichen Satz und ist zudem auch allgemeiner. Das hier effizienter gelten muss und nicht effizient sollte wohl klar sein. Wenn nicht, bitte ich den Autor hier ein effizientes Faktorisierungsverfahren zu nennen, das keinen Quantencomputer benötigt. --Squizzz 23:00, 5. Mai 2006 (CEST)

Ich halte die Aussage jetzt nicht für 100 Prozent korrekt, da in einigen Spezialfällen, auch das Fermatsche Verfahren sehr effizient und in der Tat das effizienteste ist. Ich würde daher auf die Steigerungsform verzichten und nur von effizient sprechen. In den angesprochenen Fällen sind Verfahren wie das Quadratische Sieb nicht effizienter aber annähernd gleich effizient. Bei diesem Verfahren sucht man ein Produkt der Zahlen x^2-n, das eine Quadratzahl ergibt. Dafür werden maximal N+1 Zahlen der Form x^2-n benötigt, die glatt bezüglich einer Schranke S sind und es N Primzahlen kleiner S gibt. Die Auswahl der Zahlen, die ein Quadrat ergibt, kann effizient mit Mitteln der Linearen Algebra gefunden werden.

Das tatsächlich genügend glatte Zahlen der Form x^2-n gefunden werden können, ist meines Wissens nicht exakt bewiesen. Es gibt aber heuistische Argumente, die es als sehr wahrscheinlich erscheinen lassen, dass genügen glatte Zahlen gefunden werden können, wenn die Schranke

$S=exp(ln(n)^{1/3})$

gewählt wird. Häufig wird auch eine abweichende Formel für S angegeben, die jedoch nicht verifizierbar ist. Ein Quantencomputer wird für Zahlen mit einigen 100 stellen nicht benötigt. (nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 14:14, 6. Mai 2006)

Ich habe jetzt einfach mal die Details aus dem Satz gestrichen und stattdessen geschrieben

... die in der Regel eine bessere Laufzeit aufweisen.

Dabei bleibt die Behauptung im Wesentlichen erhalten, nur die Details fehlen. Diese betreffen Eigenschaften anderer Verfahren, auf die dort eingegangen werden sollte. Vergleiche verschiedener Algorithmen wären wohl am besten im Artikel „Faktorisierungsverfahen“ aufgehoben. --Squizzz 14:33, 6. Mai 2006 (CEST)

Abschnitt „Erweiterung: Faktorisierung eines Vielfachen“

Fsswsb, was willst du mit diesem Abschnitt eigentlich sagen. Ich sehe im Moment ein schön konstruiertes Beispiel bei dem die Primfaktoren elegant bestimmet werden. Aber was bringt dieses Beispiel im Bezug auf den allgemeinen Fall? --Squizzz 22:14, 13. Apr 2006 (CEST)

Ich wollte zunächst aufzeigen, dass mit dem Fermatschen Verfahren nur spezielle Zahlen, solche die in annähernd gleich große Faktoren zerfallen, effizient faktorisiert werden können. Das Verfahren lässt sich jedoch mit einem Trick auf weit mehr Zahlen effizient anwenden. Der Trick besteht darin, nicht direkt n sondern Vielfache von n mit dem Verfahren zu faktorisieren. Häufig zerfallen diese Vielfachen dann in etwa gleich große Faktoren. Mit dem ggT können schließlich auch die eigentlich gesuchten Faktoren von n bestimmt werden.

Ich habe den Abschnitt nun stark überarbeitet und von „Verbesserung für spezielle Zahlen“ in „Weiterentwicklung: Multiplikation mit einem Faktor“ umbenannt. Mit dem Titel bin ich noch nicht ganz zufrieden. Vielleicht fällt noch jemandem ein besserer ein. --Squizzz 17:00, 21. Apr 2006 (CEST)

Der ggT(n,a') ist ein Teiler von n. Dies ist wahrlich offensichtlich und braucht nicht mittels einer sinnlosen Formel begründet werden. Der größte gemeinsame Teiler zweier Zahlen ist ein Teiler beider Zahlen. Dies bedarf keiner besonderen Erklärung.

Das Vielfache wird nicht derart berechnet, dass sich ungefähr gleich große Faktoren ergeben, sondern es wird ein Faktor k gewählt, z.B. das Vielfache meherer kleiner ungerader Primzahlen, so dass mit höherer Wahrscheinlichkeit solche Zerlegungen auftreten. Falls man die Zerlegung bereits kennt, ist die Anwendung des Verfahren schließlich sinnlos.

Die 1729 war das Zahlenbeispiel mit vielen Iterationen. Es sollte demonstriert werden, dass durch den Vorfaktor 120 eine schnellere Zerlegung erreicht wird. Der Faktor ist aber nicht speziell auf dies Zahl zugeschnitten. Eine schnellere Zerlegung wird auch mit anderen Fakoren wie 3 und 105 erreicht.

Benutzer:Fsswsb 02.05.2006

Änderung vom 01:24, 3. Mai 2006: Ich habe nun den Abschnitt noch einmal leicht verändert. Insbesondere das Beispiel weiter oben eingefügt, da zum Verständnis die Hintergründe der Erweiterung des Verfahrens nicht notwendig sind. --Squizzz 01:36, 3. Mai 2006 (CEST)

Änderung vom 19:21, 3. Mai 2006: Es wurde in der vorhergehenden Änderung die Sätze

Der Teiler 247 = 13*19 kann auch als der größte gemeinsamen Teiler von 1729 und 494 berechnet werden. Die Faktoren 13 und 19 könnten durch erneute Anwendung des Verfahrens auf den Faktor 247 mit nur einer Iteration gewonnen werden (16*16-247=9).

wieder aufgenommen, obwohl ich sie schon einmal ersetzt habe. Meine Kritikpunkte an diesen Sätzen: Es ist nur Zufall, dass hier beide Faktoren von $n'$ die gleiche Faktorisierung erzeugen. Das kommt in obigem Satz nicht zur Geltung. Im Gegenteil wird sogar der Eindruch erweckt, dass beide Teiler von $n'$ die gleich Faktorisierung erzeugen. Des Weiteren ist es in diesem Abschnitt irrelevant, dass 247 eine zusammengesetzte Zahl ist und wie ihre Primfaktorzerlegung aussieht. Deshalb habe ich diese beiden Sätze wieder ersetzt. --Squizzz 19:32, 3. Mai 2006 (CEST)

Änderungen vom 14.04

Den Sinn der letzten Änderungen kann ich nicht wirklich erkennen. Der Artikel ist jetzt wesentlich länger, ohne dass etwas wesentliches hinzugekommen ist oder der Artikel verständlicher wäre. Das Gegenteil ist der Fall. Vor allem die Geschichte mit den ungeraden Zahlen wird jetzt länglich breit getreten und völlig verwirrend dargestellt. Dabei haben sich wohl auch noch Fehler eingeschlichen. Ich denke, das beste ist ein Revert.

Benutzer: Fsswsb 14.04.06 10:00

Korrektheitsbeweis

Diesen Abschnitt halte ich auch für (weitgehend) überflüssig. Zunächst ist die Sache auch ohne lange Erklärung klar. Jede ungerade Zahl lässt sich als Produkt zweier ungerader Zahlen schreiben. Dies gilt sogar für eine Primzahl p, die als 1*p geschrieben werden kann, obgleich diese triviale Zerlegung ziemlich witzlos ist. Es ist daher sinnvoll sich auf den Fall zusammengesetzter Zahlen zu beschränken, die sich in Faktoren a und b größer als 1 und kleiner n zerlegen lassen.

Die Zerlegung n = ab lässt sich in die Form n = (x+y)*(x-y) = x^2 - y^2 mit x=(a+b)/2 und y=(a-b)/2 überführen. Die Zahlen x,y sind ganzzahlig. Dies folgt unmittelbar aus der Tatsache, dass a und b ungerade sind. Die Zahl x ist größer die Wurzel und der Algorithmus testet alle Zahlen größer als die Wurzel bis eine solche Zerlegung gefunden ist. Es ist offensichtlich, dass immer eine Zerlegung gefunden wird und zwar diejenige mit der geringsten Differenz von a und b. Streng genommen ist noch der Sonderfall a=b getrennt zu betrachten. In diesem Fall, ist die Zerlegung jedoch sofort gefunden, weil a = ${\sqrt {n}}$ und die Wurzel im ersten Schritt ohnehin berechnet wird.

Ok, falls man die Null als Quadratzahl ansieht, kann man sich die zusätzliche Abfrage in der Tat schecken.

In der Praxis hilft dies jedoch wenig, wenn z.B. eine 100-stellige Zahl zerlegt werden soll. Falls der Algorithmus mehr als ${\sqrt {n}}$ Iterationen benötigt wird er praktisch nie terminieren.

(nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 10:52, 14. Apr 2006)

Kombination mit Probedivision

Ich habe diesen Abschnitt zusammen mit einem ihn ergänzenden entfernt. Die Aussagen sind m. E. nicht kaum relevant. Die Faktorisierungsmethode von Fermat ist im Allgemeinen langsamer als die Probedivision. D. h. man sollte die Probedivision oder ein besseres Verfahren verwenden, wenn man keine Information über die Primfaktorzerlegung hat. Die Faktorisierungsmethode von Fermat ist nur von Vorteil, wenn Informationen über die Primfaktoren bekannt sind, die auf eine für die Faktorisierungsmethode von Fermat günstige Faktorisierung schließen lassen. Dann ist allerdings keine Kombination mit der Probedivision notwendig --Squizzz 11:30, 25. Apr 2006 (CEST)

Ok, ich bin damit einverstanden, dass dieser Abschnitt entfernt wurde. Die Probedivision ist auch im Falle kleiner Primfaktoren keine sehr effiziente Methode. Die Pollard-Rho-Methode ist für solche Zahlen ebenfalls geeignet und in der Regel wesentlich schneller. Die Implementierung ist nicht wirklich schwieriger als im Falle der Probedivision. Auch die Aussage, dass die Fermatsche Faktorisierungsmethode der Probedivision vorzuziehen sei, ist recht fragwürdig. Durch einen einfachen Trick, der Multiplikation mit dem Produkt der kleinsten ungeraden Primzahlen, ist das Fermatsche Verfahren für fast alle Zahlen schneller als die Probedivision. Es stellt sich allerdings die Frage, wo überhaupt die Relevanz der Faktorisierung von Zahlen mit 10 und mehr Stellen liegen soll. Für kleinere Zahlen ist der Aufwand ohnehin gering.

Vergleiche mit Probedivision

Es ist unnötig im Artikel an allen möglichen Stellen Vergleiche mit der Probedivision anzustellen, da diese meist nicht zu verallgemeinern sind. Die Faktorisierungsmethode von Fermat ist kein Verfahren für den praktischen Einsatz! --Squizzz 02:22, 2. Mai 2006 (CEST)

Benutzer Fsswsb

Ich bitte dich darum Änderungen entweder allgemein verständlich zu formulieren, oder einfach hier auf der Diskussionsseite einen Änderungsvorschlag zu unterbreiten, den ich dann kommentiere und evtl. redigiert in den Artikel aufnehme. Du hast zum Beispiel folgenden Satz in diesen Abschnitt aufgenommen:

Ist n das Produkt zweier Primzahlen P wesentlich kleiner als Q, kann eventuell $k\cdot P\approx Q$ gelten, so dass $n'$ in zwei annähernd gleich große Faktoren zerlegt werden kann. Falls jedoch $k\cdot P>Q$, wird die Faktorisierung eventuell noch langsamer.

Gelinde gesagt ist dieser schwer verständlich (was ist beispielsweise Q). Ich habe zwar ein Idee was du meinst und werde die bei Gelegenheit einbauen, doch kommt darauf wohl nicht jeder. Deshalb bitte ich dich solche Änderungen künftig zu unterlassen. --Squizzz 01:36, 3. Mai 2006 (CEST)

Leider geht die jetzige Fassung des Artikels ziemlich an der Sache vorbei. Die Idee besteht nicht darin n mit vielen unterscheidlichen Werten von k zu multiplizieren und damit eventuell eine günstige Zerlegung zu finden. Sondern man multipliziert mit einem k, dem Produkt vieler ungerader Primzahlen und eventuell der 8. Das Produkt lässt sich in den meisten Fällen in wenigen Schritten faktorisieren, während dies ohne den Faktor oft nicht möglich ist.

Ohne die Multiplikation von k kann der ungünstige Fall eintreten, dass n das Produkt zweier Primzahlen P und Q ist, wobei P sehr viel kleiner Q ist. Wird k in der Größenordnung der Wurzel aus n gewählt kann n in zwei Faktoren (kP)*(Q) zerlegt werden, die annähernd gleich groß sind.

Falls k = 3*5*7*8 gewählt wird gibt es 16 Möglichkeiten die beiden Faktoren P und Q mit diesen Faktoren zusammenzufassen wie z.B. (3*5*Q)*(8*7*P), die eventuell eine effiziente Faktorisierung erlauben.

(nicht signierter Beitrag von 84.169.239.221 (Diskussion) 23:44, 3. Mai 2006)

Könntest du bitte deine Löschungen vom 3. Mai 2006 begründen. --Squizzz 12:11, 4. Mai 2006 (CEST)

Naja, in der Zahlentheorie ... nur von theoretischem Interesse. Ist innerhalb einer Theorie nicht irgendwie alles nur von theoretischem Interesse. Ich denke es ist besser sich auf die Fakten zu beschränken. Die Erklärung mit dem k ist unsinnig, da k nicht unbedingt variieirt werden braucht (s.o.). (nicht signierter Beitrag von 84.169.222.109 (Diskussion) 13:48, 4. Mai 2006)

Es gibt auch Algorithmen der Zahlentheorie, die in der Praxis wichtig sind und eingesetzt werden. Die Faktorisierungsmethode von Fermat gehört meines Wissens nicht dazu. Das sollte die Einleitung klarstellen. Der unbedarfte Leser soll einen Eindruck von der Bedeutung des Themas erhalten. Dadurch soll auch vermieden werden, dass Leute in diesem Artikel irgendwelche Mutmaßungen über eine mögliche praktische Anwendung angeben. --Squizzz 14:30, 4. Mai 2006 (CEST)

Laufzeit

Im Fall $n=3p$ muss $x$ den Bereich von ${\sqrt {3p}}$ bis ${\frac {p+3}{2}}$ durchlaufen, und der ist $\Omega (n)$ lang. Die weitergehende Analyse habe ich gestrichen, ich verstehe auch nicht, wieso man da einfach $\log n$ hoch irgendetwas nehmen soll (der implizite Faktor bei $O(n^{1/2})$ scheint sich auch auf mysteriöse Weise in Luft aufzulösen). Der Algorithmus bleibt ja auch ziemlich vage bei dem Punkt, wie man eigentlich entscheiden soll, ob $x^{2}-n$ eine Quadratzahl ist. Bei Knuth (a.a.O. S. 317) sind als Operationen nur Additionen und Subtraktionen beteiligt, also ist die Laufzeit einfach ein kleiner Faktor ($\log n$) mal der Anzahl der Iterationen, die er als $\max\{a,b\}-{\sqrt {n}}$ angibt. Knuth verweist auch noch auf eine Verbesserung, die $O(n^{1/3})$ liefern soll, ohne aber genauer darauf einzugehen.--Gunther 01:58, 4. Mai 2006 (CEST)

Die Verbesserung scheint irgendetwas mit dem Verfahren von Lehman zu tun zu haben. Ich bin im Moment dabei mich da schlauer zu machen. --Squizzz 09:00, 4. Mai 2006 (CEST)

Im Fall der Laufzeit ist es unsinnig nur den ungünstigsten Fall zu betrachten. Der Fall n=3p ist für die Fermatmethode extrem ungünstig, aber dafür mit der Probedivision im Falle ungerader Zahlen der günstigste Fall. Diesem extrem Fall kann man jedoch den Fall gegenüberstellen, dass eine Zerlegung in annähernd gleich große Faktoren existiert. In diesem Fall ist die Fermatmethode wesentlich günstiger.

Um diesen Vorteil zu quantifizieren ist es sinnvoll $\Omega (n)$ für den Fall $a\approx b$ näher zu betrachten. Dazu kann der Ansatz

$a=(1+\delta )b$

gemacht werden. Für $\delta ^{2}$ wesentlich kleiner 1 erhält man näherungsweise

$\Omega \approx 1/8*\delta ^{2}{\sqrt {n}}$

In dieser Umformung ist offensichtlich, dass jetzt das Fermatverfahren wesentlich günstiger als die Probedivision ist, da z.B. im Fall n = PQ mit den Primzahlen P und Q annähernd $min(P,Q)\approx {\sqrt {n}}$ Iterationen erforderlich sind. Durch Rückeinsetzen von $\delta ={\frac {a-b}{b}}$ erhält man

$\Omega \approx {\frac {(a-b)^{2}}{8b}}$

In dieser Form ist erkennbar, dass für große Zahlen das Verfahren auch günstiger ist als die Probedivision absteigend mit ${\sqrt {n}}$ beginnend.

Für kleine Zahlen bis zu einigen tausend ist die Laufzeit in jedem Fall unerheblich. Selbst im ungünstigsten Fall n=3p ist die Berechnung wahrscheinlich noch schneller als die Anzeige der Zahlen. Für sehr große Zahlen mit 100 Stellen und mehr ist die Probedivision im Fall zweier großer Primzahlen jedoch aussichtslos. Die Fermatmethode ermöglich hier jedoch die Faktorsierung in einigen Spezialfällen. Die Zahl dieser Spezialfälle kann noch erheblich erhöht werden, wenn nicht n sondern n multipliziert mit 8 und den kleinsten ungeraden Primzahlen faktorisiert wird.

Im allgemeinen Fall ist für 100-stellige Zahlen das Quadratische Sieb erforderlich. (nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 10:33, 4. Mai 2006)

Auch ${\frac {\delta ^{2}}{8}}{\sqrt {n}}$ ist im wesentlichen ${\sqrt {n}}$, solange $\delta$ nicht irgendwie für große $n$ kleiner wird. Abgesehen davon führen nach üblichem Verständnis "ungefähr gleich große" Primfaktoren halt nicht zu einem ausreichend kleinen δ, beispielsweise bei en:RSA-129 ist $\delta \approx 8$.--Gunther 11:18, 4. Mai 2006 (CEST)

Falls n mit den kleinsten Primzahlen und der 8 multipliziert, besteht eine gute Chance, dass $\delta$ sehr klein wird. Falls $\delta \approx 8$ veringert sich der Wert auf $\delta \approx 0,1$ für n' = 120n mit der Aufteilung (30*P)(4*Q). Allerdings ist $\delta$ unbekannt, so dass man hier nur auf den Zufall hoffen kann. Die Wahrscheinlichkeit, dass sich die Laufzeit gegenüber der Probedivision deutlich verbessert ist sehr hoch. Allerdings genügt dies in den meisten Fällen nicht, um eine 100 stellige Zahl faktorisieren zu können. (nicht signierter Beitrag von 84.169.221.234 (Diskussion) 13:26, 4. Mai 2006)

Um die Erweiterung geht es in dem fraglichen Abschnitt noch nicht, die kommt erst weiter unten. Und ohne irgendwelche Belege, die das möglichst auch noch irgendwie quantifizieren, ist das alles viel zu vage.--Gunther 13:32, 4. Mai 2006 (CEST)

Wieso, ich denke was jetzt im Artikel steht ist schon ok. Für ein $\epsilon$ wesentlich kleiner 1 ist die Abschätzung korrekt. Für $\epsilon =1$ ist der Faktor sogar noch kleiner ($1,5-{\sqrt {2}}$) statt 0,5. (nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 14:57, 4. Mai 2006) Wir können uns auch nochmal die Abschätzung für die Zahl der Rechenschritte genauer ansehen.

$\Omega (n)\approx {\frac {(a-b)^{2}}{8b}}$

Die Bedingung für eine effiziente Faktorisierung könnte man folglich als

${\frac {(a-b)^{2}}{8b}}\approx 1$

formulieren. In diesem Fall gilt zudem $b\approx {\sqrt {n}}$. Die Faktorisierung ist effizient falls (a-b)/8 maximal in der Größenordnung von $O(n^{1/4})$ liegt. Bei einer 100-stelligen Zahl darf die Differenz nur etwa 25-Stellen aufweisen. Betrachtet man zusätzlich die Multiplikation mit kleinen Vielfachen, dann muss es kleine Zahlen k1,k2 geben, so dass k1*P-k2*Q maximal in der Größenordnung von $O(n^{1/4})$ liegt.

Nachprogrammierung des Algorithmus

Bei der Beschreibung -> 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. <- verstehe ich, dass es 22 Zahlen gibt:

00,01,21,41,61,81,04,24,44,64,84,25,16,36,56,76,96,09,29,49,69 und 89

die eine Quadratzahl ausmachen (am Ende von r). Hier wird ein Beispiel mit der Zahl 1729 vorgeführt. Wir fangen mit x = 42 und gehen immer wieder höher. Doch mein Programm beendet die Suche nach der Zahl 1296, bei x = 45. Das kann ich auch nachvollziehen, da die Zahl r in diesem Moment 296 beträgt und laut dem Ausschussverfahren ist dies eine Quadratzahl. (nicht signierter Beitrag von 88.152.172.30 (Diskussion) 00:18, 8. Mär. 2011 (CET))