Warum funktioniert dieser Faktorisierungs-Algorithmus? |
16.06.2020, 11:41 | MaPalui | Auf diesen Beitrag antworten » | ||
Warum funktioniert dieser Faktorisierungs-Algorithmus? 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. |
||||
16.06.2020, 12:56 | 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 ? |
||||
16.06.2020, 13:06 | 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:
t^2 ist ja gerade m |
||||
17.06.2020, 23:11 | 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 |
||||
19.06.2020, 17:13 | 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 Wäre sehr nett wenn ich dann auch nochmal reinschauen könntet LG Eure Maren |
||||
30.06.2020, 12:19 | MaPalui | Auf diesen Beitrag antworten » | ||
Hi URL 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 Edit: Das war vielleicht zu voreilig. Am Ende gilt doch: für ein . Gut, und nun den ggT berechnen Ich check es einfach nicht, |
||||
Anzeige | ||||
|
||||
30.06.2020, 23:07 | 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? |
||||
01.07.2020, 00:21 | MaPalui | Auf diesen Beitrag antworten » | ||
Es ist ein deterministischer Algorithmus, also er findet immer einen Teiler. |
||||
01.07.2020, 15:49 | 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
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 Bin ich denn weit entfernt? Ich danke euch allen ganz vielmals. Ich könnt' euch knutschen Maren |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|