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

Abschnitt: Verbesserung für spezielle Zahlen

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.

Ä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. Dies gilt zumindest für einen hypothetisch unendlich schnellen Rechner.

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.