Warum funktioniert dieser Faktorisierungs-Algorithmus?

Neue Frage »

MaPalui Auf diesen Beitrag antworten »
Warum funktioniert dieser Faktorisierungs-Algorithmus?
Hallo liebe Leute,

ich verzweifle vollkommen an Hart's One-Line-Algorithmus. Ich verstehe einfach nicht, warum er funktioniert. Auch Beispiele haben mir leider keine Erkenntnisse gebracht.
Ich wäre euch so sehr dankbar wenn mir jemand den Ansatz nenne könnte, mit dem ich weiterarbeiten kann.
Der Algorithmus ist dieser:
[attach]51513[/attach]

Ok, ich geben die zu faktorisierende Zahl an und eine Anzahl an Iterationen .
Die Variable erhält nun die aufgerundete Wurzel von .
Und es wird gesetzt:
Aber was bringt das?

Da Du diese Frage bereits im März gestellt hast, schließe ich den alten Thread nun. Steffen

Edit:
Danke Steffen. Ja, ich bin immernoch am gleichen Punkt und komme einfach nicht weiter :'( Ich hoffe, das war ok, einen neuen Thread aufzumachen.
Elvis Auf diesen Beitrag antworten »

Genügt das als Erklärung: http://wrap.warwick.ac.uk/54707/1/WRAP_H...8712000146a.pdf ? Wenn nicht, warum nicht ?
MaPalui Auf diesen Beitrag antworten »

Hallo Elvis,

danke sehr. Aber genau das ist meine Quelle. Hatte oben nur aus Sekundärliteratur zitiert. Von daher werde ich mal konkreter mit meinen Fragen, sorry...
Ausgehend von der von dir genannten Quelle:

Wenn ich mal Zeile 3 betrachte und davon ausgehe, ist ein Quadrat, dann gilt doch:

Also ist


Ich bin wahrscheinlich blind, aber ich sehe nicht, wie mir das auf der Suche nach einem Teiler weiterhilft.

Unten steht ja noch:
Zitat:
In alternative terms, we search for a solution to by iterating i and looking for squares after reduction modulo n.


t^2 ist ja gerade m verwirrt
URL Auf diesen Beitrag antworten »

Aus folgt also ist n Teiler von . Von daher ist es plausibel nach dem ggT von n und s-t zu suchen. Mehr fällt mir dazu gerade nicht ein verwirrt
MaPaLui123 Auf diesen Beitrag antworten »

Hallo ihr lieben,

ich danke euch sehr für eure Antowrten, schaue mir die aber am Wochenede ganz in Ruhe an. Bin gerade unterwegs Big Laugh

Wäre sehr nett wenn ich dann auch nochmal reinschauen könntet smile

LG
Eure Maren
MaPalui Auf diesen Beitrag antworten »

Zitat:
Original von URL
Aus folgt also ist n Teiler von . Von daher ist es plausibel nach dem ggT von n und s-t zu suchen. Mehr fällt mir dazu gerade nicht ein verwirrt


Hi URL smile
vielen Dank für deine Anmerkung und bitte entschuldigt alle meine viel zu späte Antwort.

Mit deiner Argumentation habe ich nun auch die Frage nach dem ggT verstanden.
Was mich nun noch wundert: Ich suche doch einen Teiler von .
Das also selbst ein Teiler von ist, macht mich gerade stutzig was mir das genau sagen soll verwirrt

Edit:
Das war vielleicht zu voreilig.
Am Ende gilt doch: für ein .

Gut, und nun den ggT berechnen verwirrt
Ich check es einfach nicht,
 
 
URL Auf diesen Beitrag antworten »

Nehmen wir an, p ist echter Primteiler von n. Dann ist p auch Teiler von (s-t)(s+t), also Teiler eines der beiden Faktoren.
Wenn n kein Teiler von s+t ist, dann gibt es einen Primteiler p von n, der Teiler von s-t sein muss. In dem Fall ist ggT(n,s-t) also ein Vielfaches von p, also ein nichttrivialer Teiler von n (außer es wäre ggT(n,s-t)=n).

Die Frage ist also, ob man begründen kann, dass n weder Teiler von s+t noch von s-t ist.
Was ist denn eigentlich die Aussage des Algorithmus? Dass man immer einen Teiler von n findet? Oder nur mit einer gewissen Wahrscheinlichkeit?
MaPalui Auf diesen Beitrag antworten »

Zitat:
Original von URL
Was ist denn eigentlich die Aussage des Algorithmus? Dass man immer einen Teiler von n findet? Oder nur mit einer gewissen Wahrscheinlichkeit?


Es ist ein deterministischer Algorithmus, also er findet immer einen Teiler.
MaPalui Auf diesen Beitrag antworten »

Also, ich möchte gerne nochmal mit meinen eigenen Worten wiedergeben, was ich erkenne. Bitte entschuldigt wenn das nun doppelt kommt.

Wir haben eine Zahl .
Betrachten wir nun für ein .
Bilden wir

Nun ist natürlich größergleich .
Schreiben wir also .
(An dieser Stelle liefert mir die Betrachung (mod n) also genau die Differenz zurück).

Ist nun ein Quadrat, also , dann:
.

Und nun bilden wir also .

Bis hierhin ist das doch die Rechnung, oder?

Annahme:
hat einen echten Teiler , also .
Dann gilt: oder .
Nehmen wir nun'oBdA an, teile nicht .
Dann teilt aber .
Also ist der für ein k und damit ein nichttrivialer Teiler von .
Achja, endlich habe ich das mal verstanden! Super! Vielen Dank bis hierher!


Achso, und daher stellst du nun auch die
Zitat:
Frage ist also, ob man begründen kann, dass n weder Teiler von s+t noch von s-t ist.
.

Also, gelte nun, teiler weder , nocht .
Gut, dann ist natürlich das gefundene ein Teiler von einem der beiden Faktoren.

Ok, das bringt schon viel mehr Licht in die Sache.
Auch wenn ich nun an der letzten Frage noch grüble verwirrt Bin ich denn weit entfernt?

Ich danke euch allen ganz vielmals. Ich könnt' euch knutschen Big Laugh

Maren
Neue Frage »
Antworten »



Verwandte Themen

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