Fermats Faktorisierungsverfahren, Differenz zweier Quadrate

Neue Frage »

ichwarneu Auf diesen Beitrag antworten »
Fermats Faktorisierungsverfahren, Differenz zweier Quadrate
Hallo zusammen,

ich schaue mir gerade Fermats Verfahren zur Faktorisierung an. Dazu hier der Ausschnitt aus der Quelle die ich nutze:
[attach]53336[/attach]

Mir ist auch klar, wie das ganze funktioniert. Aber eine Sache erschließt sich mir nicht:
Warum spuckt der Algorithmus "FALSE", also "prim" aus, wenn vorliegt?
Das ich bei einer Primzahl nur diese Faktorisierung erhalte, ist klar.
Aber auch jede andere Zahl lässt sich doch mit trivial faktorisieren.
Warum ist im Algorithmus ausgeschlossen, dass eine Nichtprimzahl diese Faktorisierung liefert? verwirrt

Viele Grüße
ichwarneu
ichwarneu Auf diesen Beitrag antworten »

Hallo nochmal,

ich scheitere leider immernoch hieran und bin kein Stück weitergekommen.
Kann mir jemand vielleicht einen Ansatz für einen Beweis nennen?
Oder die Vorgehensweise?

Ich frage mich, warum sichergestellt ist, dass der Algorithmus mir immer einen Teiler bringt und keinen "überspringt"?
Ich hatte es versucht mit einem indirekten Beweis.
Aber da weiß ich alleine den Ansatz nicht,
IfindU Auf diesen Beitrag antworten »

Ich habe es mal aus Spaß mit der Primzahl versucht.

Ich bekomme im Anfang . Nach ein paar Iterationen bekomme ich und damit und . Zwar gilt dann offensichtlich , aber .

Irgendwas ist da krumm mit der Aussage. Wäre in dem Fall , dann würde folgen, dass ist, was es ja nicht sein kann. Ich würde daher vermuten es ist prim, wenn ist. Damit ist dann mit eine triviale Zerlegung gefunden. Dann könnte man mit Monotonie versuchen zu argumentieren, dass man vor dieser trivialen Zerlegung, sofern existent, immer eine andere findet.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
Warum spuckt der Algorithmus "FALSE", also "prim" aus, wenn vorliegt?

Bist du dir sicher, dich hier nicht verschrieben zu haben (x+y statt x)? prim bedeutet nämlich, es gibt nur die Faktorisierung , was aufgelöst

und

ergibt.


Übrigens: Wenn ich mal den "Effizienzblick" auf den Algorithmus werfe, dann stutze ich bei Zeile 4:

Die Entscheidung "r ist kein ganzzahliges Quadrat" ist m.E. von der Komplexität her ein gewaltiger Brocken, gegen den der Rest hinsichtlich Aufwand nahezu verblasst. Augenzwinkern
ichwarneu Auf diesen Beitrag antworten »

Hallo ihr zwei,

ich danke euch vielmals für eure Zeit. Ich bin gerade im Zug unterwegs, aber werde gleich nochmal auf den Algorithmus schauen. Wenn euch das aber aufgefallen ist, werde ich mich da sicherlich verschrieben haben. Das korrigiere ich natürlich gleich.

Edit: Ihr habt natürlich Recht, es muss heißen.

@HAL 9000:
Danke für den Hinweis mit Zeile 4.
Fermat hat es ja so gemacht, dass er die letzten beiden Ziffern betrachtete und damit potentielle Nichtkandidaten (sagt man das so?) von vornherein ausschließen konnte.
Heuristisch macht das etwa 80% aller auftretenden Reste aus.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
Fermat hat es ja so gemacht, dass er die letzten beiden Ziffern betrachtete und damit potentielle Nichtkandidaten (sagt man das so?) von vornherein ausschließen konnte.
Heuristisch macht das etwa 80% aller auftretenden Reste aus.

Ok, auf die heutige Binärarchitektur "übersetzt" kann man das vielleicht so adaptieren:

Man betrachtet (durch AND-Maskierung) die letzten Binärstellen der Zahl und entscheidet anhand einer LUT (look-up table) für die quadratischen Reste modulo ), ob es ggfs. ein Quadrat ist. In diesen Fällen muss man dann doch weiter untersuchen, in den anderen nicht. Wie groß man wählt wird dann im wesentlichen davon bestimmt, wieviel Platz man der LUT spendieren will bzw. kann. Augenzwinkern
 
 
ichwarneu Auf diesen Beitrag antworten »

Zitat:
Original von IfindU
Dann könnte man mit Monotonie versuchen zu argumentieren, dass man vor dieser trivialen Zerlegung, sofern existent, immer eine andere findet.


So war auch schon meine Überlegung.
Behauptung: Fermats Algorithmus findet zuerst eine nichttriviale Faktorisierung von N, falls es diese gibt. Gibt es keine, wird auf jeden Fall die triviale Faktorisierung ausgegeben.

Sei N prim. Dann gibt es nur die triviale Zerlegung .
Wendet man nun Fermats Algorithmus an...

Ja, und hier scheitere ich nun leider unglücklich
Ich habe es auch an einigen Beispielen gerechnet aber mit ist formal nicht klar, warum ich nicht in eine Endlosschleife geraten könnte verwirrt

Zitat:
Original von HAL 9000
Ok, auf die heutige Binärarchitektur "übersetzt" kann man das vielleicht so adaptieren:

Man betrachtet (durch AND-Maskierung) die letzten Binärstellen der Zahl und entscheidet anhand einer LUT (look-up table) für die quadratischen Reste modulo ), ob es ggfs. ein Quadrat ist. In diesen Fällen muss man dann doch weiter untersuchen, in den anderen nicht. Wie groß man wählt wird dann im wesentlichen davon bestimmt, wieviel Platz man der LUT spendieren will bzw. kann. Augenzwinkern


Ich habe noch nie von LUT gehört, aber ich denke ich weiß, was dahintersteckt.
Mit festem habe ich es auch implementiert, um Fermats Vorgehen verdeutlichen zu können.
IfindU Auf diesen Beitrag antworten »
RE: Fermats Faktorisierungsverfahren, Differenz zweier Quadrate
Die ganze Idee ist, dass jedes berechnete Paar (t,r) eine Lösung (x,y) liefern mit . Es ist sogar , aber leider mit i.A.; man nimmt nun das aller erste . Nun wachsen mit jedem Schritt und es gilt immer . D.h. die größte Lösung ist der Trivialfall, und jede Lösung davor ist eine mögliche Faktorisierung.

Dass es alles durchläuft, sieht man daran, dass alle "relevanten" ungeraden Zahlen durchläuft. Du könntest auch unabhängig von immer mit und starten. Allerdings wird kein ein positives liefern, geschweige quadratisch.

Der größere Sprung in ist die Anpassung, damit man die Eigenschaft beibehält.
ichwarneu Auf diesen Beitrag antworten »

Danke für diese Erklärung. Ich werde das später oder morgen nochmal aufschreiben und würde mich freuen, wenn ihr nochmal reinschauen könntet.
Danke euch und schönen abend smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
Aber auch jede andere Zahl lässt sich doch mit trivial faktorisieren.

Um die Gedanken von IfindU anhand dieses Beispiels konkret zu vertiefen: Jede ungerade zusammengesetzte Zahl mit dann ebenfalls ungeraden Faktoren erfüllt ja eben auch

,

und es ist (folgt durch Umstellung aus ), d.h., jenes wird im Algorithmus EHER erreicht.
ichwarneu Auf diesen Beitrag antworten »

Hallo HAL 9000,

danke für diesen weiteren Hinweis.
Ich muss mir das nochmal auf Papier genau aufschreiben, das werde ich morgen machen.
Meine Befürchtung ist dass ich dann die Frage stelle warum es sichergestellt ist, dass der von dir genannte Faktor auch erreicht wird.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
warum es sichergestellt ist, dass der von dir genannte Faktor auch erreicht wird.

Weil in jedem Schleifenschritt (von beginnend) der Wert nur um 1 inkrementiert wird:

Denn auch wenn in der Schleife gar nicht mehr explizit vorkommt, so kann man es sich doch implizit hinzudenken über dieses zu jedem Schleifenzeitpunkt geltende : Die Inkrementierung von jeweils um 2 entspricht dieser (impliziten) Inkrementierung von um 1. Ausführlicher ist Schritt



genau genommen die Kurzvariante (weil weniger rechenaufwändig) von




Und wenn immer nur um 1 inkrementiert wird, kann man den Wert auch nicht "verpassen". Bleibt nur die Frage zu klären, warum auf jeden Fall ist, d.h., mindestens so groß wie der Startwert des Verfahrens - das kannst du dir mal noch überlegen.
ichwarneu Auf diesen Beitrag antworten »

Ja, die Inkrementation verstehe ich. Es wird sukzessive
,


gebildet, bis ein auftrendes ein Quadrat ist.
Dann liegt die Faktorisierung nach dritter binomischer Formel vor.

Aber bevor ich jetzt weiter aushole, schreibe ich mir das lieber morgen nochmal auf. Sonst frage ich jetzt nur Sachen, die ihr schon beantwortet habt und das wäre mir nicht recht.

Danke dass ihr so spät hier noch reinschaut smile
ichwarneu Auf diesen Beitrag antworten »

Hallo zusammen,

bitte entschuldigt meine Verspätung. Es kam leider doch etwas dazwischen.
Ich werde mich nun aber nochmal mit dem Problem befassen und würde mich noch heute hier zurückmelden.
Würde mich freuen wenn ihr nochmal reinschauen könntet, natürlich nur wie ihr Zeit habt.

Nochmals Sorry dass die Antwort jetzt nicht gewünscht einen Tag später kam.
ichwarneu Auf diesen Beitrag antworten »

So, nun aber mein Ansatz bisher:

Sei eine feste, ungerade natürliche Zahl. Bilde dann .
Für alle bilde . Dann bildet jedes Paar eine Lösung der Form .
Die lassen sich gemäß der Vorgabe für explizit berechnen.
Nach Schritten liegt die triviale Faktorisierung vor, denn .
Da , terminiert der Algorithmus in jedem Fall, spätestens mit der trivialen Faktorisierung.

Es bleibt nun zu zeigen, dass eine mögliche Faktorisierung vorher erwischt wird. Dazu habt ihr mir ja bereits einige Hinweise gegeben, die ich aber noch nicht sauber aufschreiben konnte. Das würde ich aber noch machen.

Ist dieser Ansatz bisher ok?
IfindU Auf diesen Beitrag antworten »

Für ist und damit nur im komplexen Sinne definiert. Das würde ich separat betrachten bzw. weg argumentieren.

Ansonsten passt es aus meiner Sicht bis auf klein Tippfehler ( statt korrekterweise ) Freude
ichwarneu Auf diesen Beitrag antworten »

Ich danke dir. Die Einwände verstehe ich voll und ganz.
Gut, damit konnte ich nun zeigen dass schlimmstenfalls die triviale Faktorisierung Auftritt.

Falls es eine weitere gibt, wird sie vorher gefunden. Am sauberen Beweis arbeite ich gerade.
ichwarneu Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Und wenn immer nur um 1 inkrementiert wird, kann man den Wert auch nicht "verpassen". Bleibt nur die Frage zu klären, warum auf jeden Fall ist, d.h., mindestens so groß wie der Startwert des Verfahrens - das kannst du dir mal noch überlegen.


Guten Tag,
Ich bin auf einer langen Zugfahrt nur mit Smartphone. Daher kann ich aktuell keine sauberen Latex Formeln einfügen.
Die von dir genannte Ungleichung konnte ich zeigen mit dem Ansatz
(1/4)*(a-b)^2 >= 0

Ich habe auch gerade einen Verdacht was du mit "man kann den Wert nicht verpassen" meinst. Aber das muss ich mir erst aufschreiben.
Mir fällt das Thema nicht leicht, aber ich bin dank eurer Hilfe viel weiter und bleibe dran!
ichwarneu Auf diesen Beitrag antworten »

Ah, ich glaube ich habe es.
Sei n=ab.
Nach genau
(1+ab)/2 - x
Schritten erhalte ich die triviale Faktorisierung.
Gibt es eine nicht triviale Faktorisierung, so erhalte ich diese nach
(a+b)/2 - x
Schritten. Mit der von HAL 9000 angesprochenen Ungleichung kann ich nun schliessen, dass diese Faktorisierung EHER Auftritt, da (a+b)/2 - x eine natürliche Zahl ist und insbesondere kleiner als (ab+1)/2 -x.

Ist das die Richtung in die ihr mich stupsen wolltet?

P.S. bitte entschuldigt die vielen Antworten hintereinander. Ich habe auch überlegt, immer meine letzte Antwort zu editieren. Aber das bekommt man als Helfer im Nachhinein nicht mit, oder?
IfindU Auf diesen Beitrag antworten »

Von meiner Seite passt es Freude
ichwarneu Auf diesen Beitrag antworten »

Guten Tag zusammen,

ich habe das mal mit einem Skript überprüft und es passt genau.

Ihr habt mir wirklich sehr geholfen und ich habe wirklich was gelernt.
Ich danke euch vielmals! smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »