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
ichwarneu Auf diesen Beitrag antworten »

Da bin ich nochmal. Ich hoffe es ist ok, wenn ich diesen Thread nochmal nach oben hole.

Das Verfahren ist mir Dank eurer Hilfe nun wirklich klar geworden. Eine Frage habe ich nun allerdings noch.
Es ist ja so, dass Fermats Algorithmus den Teiler findet, der am nächsten zur Wurzel der Eingabe liegt. Nun würde ich das gerne formalisieren, stoße dabei aber auf eine Unklarheit.

Seien und alle ungerade. Weiterhin gelte . Bilde und
Nun haben wir herausgefunden dass Fermats Verfahren nach Schritten die Faktoren und findet.
Einfache Nachrechnung ergibt , also werden diese beiden Faktoren als erstes aufgefunden.

Nun meine Frage:
Ich weiß doch nicht, ob nun der Faktor oder am nächsten zur Wurzel der Eingabe liegt, oder?
Ich weiß ja nur, dass diese Faktoren zuerst aufgefunden werden.
Sagen wir, ich finde zuerst die Faktoren und .
Wenn ich nun weitergehe, finde ich und .
Jetzt könnte es doch sein, dass (erster Fund) am nächsten zur Wurzel liegt, trotzdem aber einer der Faktoren des zweiten Fundes näher zur Wurzel liegt als (erster Fund).

Oder übersehe ich was? verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
Wenn ich nun weitergehe, finde ich und .

Wieso gehst du überhaupt weiter? Mit den Finden der beiden Faktoren und (von denen wir zu dem Zeitpunkt noch nicht wissen, ob sie prim oder doch noch weiter zerlegbar sind) íst doch die Fermat-Faktorisierung von beendet!

Falls du damit die komplette Primfaktorzerlegung deiner Zahl ermitteln willst, dann musst du mit dem erhaltenen Ergebnis verzweigen in die beiden neuen Faktorisierungen von sowie - so würde ich zumindest "Primfaktorzerlegung per Fermat-Faktorisierung" verstehen! verwirrt
ichwarneu Auf diesen Beitrag antworten »

Hallo HAL, danke für deine Zeit.
Sorry, die Frage ist wirklich ungünstig formuliert.
Ich komme nach Schritten zur Faktorisierung .
Aber was weiss ich nun?
Weiss ich, dass einer der Faktoren oder näher zur Wurzel der Eingabe liegt als Alle anderen möglichen Faktoren?
HAL 9000 Auf diesen Beitrag antworten »

Hmm, ich dachte ich hätte mich klar geäußert, nochmal von vorn: Du hast mit (wie ich annehme) Primzahlen mit .

Die Fermat-Faktorisierung stoppt nun bei mit , aber wir wissen zu diesem Zeitpunkt NICHT, ob wir Situation oder aber vorliegen haben. Das offenbart erst eine weitere Analyse der beiden Faktoren : Ist prim, dann war es letztere Situation, sonst hingegen erstere.

Zitat:
Original von ichwarneu
Weiss ich, dass einer der Faktoren oder näher zur Wurzel der Eingabe liegt als Alle anderen möglichen Faktoren?

Na das auf jeden Fall: Es gilt stets und , und was die Verzahnung der beiden Ungleichungsketten betrifft, so geht allenfalls



oder



denn es gilt ja für alle Primzahlen . Mehr Fälle gibt es nicht.
ichwarneu Auf diesen Beitrag antworten »

Ich glaube die letzten beiden Ungleichungen sind das, was ich brauchte.
In Ruhe werde ich das nochmal aufschreiben und mich in jedem Fal zurückmelden. Vielen Dank für die Hilfe! Wink
ichwarneu Auf diesen Beitrag antworten »

Ok, da bin ich nochmal.
Also deine Aussage nach meinem Zitat war genau das, was ich wissen wollte. Vielen Dank dafür an dieser Stelle.

Nun habe ich mich allerdings gefragt, ob ich das nicht doch etwas zu kompliziert aufgezogen habe.
Hätte ich mit gearbeitet, wobei a und b natürliche Zahlen sind (nicht notwendigerweise prim) und gelte, dann hätte ich eine Faktorisierung nach Schritten erhalten.
Aber nun weiß ich ja an dieser Stelle noch nicht, ob oder näher an der Wurzel liegt.

Ich versuche gerade ein Argument zu finden, warum dieses Verfahren als ersten diejenige Faktorisierung findet, bei der einer der beiden Teiler derjenige ist, der am nächsten zur Wurzel liegt.
Wahrscheinlich ist es einfacher, über Monotonie zur argumentieren, denn ich bewege mich ja sukzessive vom Startwert weg. Jede andere Faktorisierung kann also nur Faktoren haben, die weiter weg liegen.
Sorry wenn ich mich etwas umständlich ausdrücke.

Edit: Vielleicht formuliere ich meine "Bedenken" mal so:
Fermats Verfahren findet nach Schritten eine Faktorisierung. Aber damit ist mir der Abstand von beziehungsweise zur Wurzel der Eingabe noch nicht bekannt.
Neue Frage »
Antworten »



Verwandte Themen

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