Faktorisierung - Pollards rho-Method |
17.01.2010, 11:00 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Faktorisierung - Pollards rho-Method es geht um folgende Aufgabe: Gegeben sei eine RSA-Zahl deren kleinster Primteiler 97 Dezimalstellen hat. Die Zahl lässt sich mit dem Pollardschen rho-Verfahren in 4 Schritten durch geeignete Wahl von a und x0 faktorisieren mit 1 <= a,x0 <= 30. Das Pollardsche Rho-Verfahren ist nicht so schwierig und ich habe versucht es in Maple zu implementieren. Ich komme aber leider nicht auf das richtige Ergebnis und finde als ggT immer nur 1. Hier mal die Zahl N und mein Code. Könnte mir bitte jemand weiterhelfen? Wo liegt mein Fehler?
Gruß |
|||||||||||||||||
17.01.2010, 12:07 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
RE: Faktorisierung - Pollards rho-Method
Dein Fehler liegt darin, dass du vom Programmieren (ob nur in Maple, oder auch sonst, sei dahingestellt) herzlich wenig Ahnung hast... Du brauchst hier keine Arrays, sondern einfache Variable x und y reichen vollkommen aus... Und warum nur 7 Schleifendurchläufe? Der Hauptfehler liegt aber darin, dass du den vorgegebenen Bereich für a und x0 nicht vollkommen überdeckt hast, also eigentlich ein logischer Fehler... Und ja, so unglaublich es klingt, Pollard's rho-Methode führt für geeignete Parameter tatsächlich zum Ziel, hab das grad selbst in Derive (und inzwischen auch Maple) gecheckt... Edit: Möchte meine anfängliche Kritik ein wenig zurücknehmen... Das Programm ist zwar wirklich keine Glanzleistung (u.a. wird auch der Bildschirm beim Aufruf mit ca. 900 Zeilen "zugepflastert"), es würde aber laufen, wenn du den Bereich für l und k richtig eingegeben hättest... |
|||||||||||||||||
17.01.2010, 15:00 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Na gut l und k könnte ich auch bei 1 beginnen lassen. Warum sollte es nicht mit arrays funktionieren? Ist doch kein großer Fehler, außer das ich mehr Speicher brauche! Außerdem habe ich tatsächlich nicht so viel Ahnung und es wäre toll, wenn mir jemand sagen könnte wie es funktioniert! So schwer ist es ja offensichtlich nicht. Danke |
|||||||||||||||||
17.01.2010, 16:06 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Wie ich oben schon geschrieben habe, ist das der Hauptfehler...Unglaublich aber wahr: Selbst mit deinen nur 7 Schleifendurchläufen gäbe es Werte für l und k, wo hier die rho-Methode fündig wird, nämlich für l=10 und k=1...Aber gerade den Wert k=1 hast du ja explizit ausgeschlossen...
Warum ist die rho-Methode so ungeheuer beliebt, sodass sie praktisch in allen CAS als erstes nach der Aussiebung von "kleinen" Primfaktoren angewandt wird? Anwort: Weil der Speicherplatzbedarf praktisch 0 ist... Bei jedem Iterationsschritt werden nur die momentanen Werte von x und y überschrieben, aber es wird kein neuer Speicher benötigt...Genau das machst du aber mit deiner Implementierung zunichte...
Ne, so schwer ist es wirklich nicht... Hier nochmals der Vollständigkeit halber alle Punkte: - Schreibe indizierte Elemente ohne jeden Index, also z.B. x statt x[i]... - Lass die Schleifen von l und k bei 1 beginnen - Mach eine eigene Zuweisung d:=igcd(x-y,N); - Ersetze den print-Befehl durch if d>1 then print(l,k,d) end if; |
|||||||||||||||||
17.01.2010, 19:26 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Danke! |
|||||||||||||||||
19.01.2010, 15:14 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Hi mystic, ich habe das Verfahren nun implementiert und versuche es auf weitere RSA-Zahlen anzuwenden. Leider ohne Erfolg. ich setze die relevanten Variablen x,y und d vor Beginn der Schleifen alle gleich 0. Ich habe es nun so implementiert:
Für die obengenannte RSA-Zahl liefert mir das ganze ein Ergebnis - ohne Probleme. Doch bei den folgenden beiden Zahlen funktioniert es einfach nicht. Kannst du mir sagen warum?
Schönen Gruß |
|||||||||||||||||
Anzeige | |||||||||||||||||
|
|||||||||||||||||
19.01.2010, 16:31 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Die rho-Methode ist im Normalfall zur Auffindung von Primfaktoren mit einer Stelligkeit von höchstens etwa 12-15 geeignet...Dass es für deine erste Zahl funktioniert hat ist eine riesige Ausnahme (wie eigentlich schon oben erwähnt) und zeigt eigentlich nur, dass dieses Beispiel in extremer Weise "konstruiert" war... Normalerweise geht für RSA-Zahlen dieser Größenordnung nur mehr eine einzige Faktorisierungsmethode, nämlich das Zahlkörpersieb (engl. NFS)... |
|||||||||||||||||
19.01.2010, 18:16 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Hi Mystic, ich denke das liegt hauptsächlich an der Kontruktion meiner RSA-Zahlen, dass sie funktionieren sollten. Die drei angegebenen Zahlen kann man schon nach 4 Schritten!!! mit diesem Verfahren faktorisieren. Das steht so in der Aufgabe. Bei den Zahlen N2 und N3 hat der kleinste Primfaktor 135 bzw. 136 Dezimalstellen. Hilft das weiter? Es muss wirklich damit funktionieren. Ansonsten gebe ich dir Recht. Gruß |
|||||||||||||||||
19.01.2010, 19:00 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Ja, sind echt sonderbare Zahlen, die du da hast, würde mich interessieren wie der "Erfinder" des Beispiels auf die gekommen ist... Bei N3 werde ich nämlich tatsächlich nach nur 4 Schleifendurchläufen für k=2, l=26 fündig, was einen 136 stelligen Faktor ergibt... Edit: N2 liefert (im zweiten Anlauf nach einem Kopierfehler) nach ebenfalls nur 4 Schleifendurchläufen für k=19, l=25 einen 135-stelligen Faktor... Edit2: Sehe gerade, du hast in deinem neuem Programm die Rollen von k und l vertauscht, sehr schlau, denn das trägt einigermaßen zur Verwirrung bei... |
|||||||||||||||||
19.01.2010, 21:21 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Hi kann morgen mal nachfragen wie der Dozent die Zahlen konstruiert hat. Sorry für die Verwirrung. Hatte den Code auf verschiedenen Rechnern mehrmals neu aufgesetzt. Ist ja ziemlich kurz das Ganze. Mich würde interessieren wie du auf die k's und l's gekommen bist und mein Programm nicht funktioniert und bei N1 schon |
|||||||||||||||||
19.01.2010, 22:32 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Wie ich's ja eigentlich schon angedeutet habe, hast du k und l vertauscht mit fatalen Folgen... Die Vorstellung, man könte da einfach etwas ungestraft vertauschen ist schlichtweg naiv...Meiner Meinung nach kannst du das am einfachsten "reparieren", indem du Zeile 2 und 3 im letzten Programm ebenfalls austauscht... |
|||||||||||||||||
20.01.2010, 12:08 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Meiner Meinung nach sind k und l nur Variablen und diese habe ich zwar vertauscht, aber der Code an sich blieb doch konsistent. Überall wo zu erst ein l steht, steht nun ein k und umgekehrt. Solange es konsistent bleibt ist das doch egal. Verwendest du Maple oder Derive und welchen Code nimmst du? Gruß |
|||||||||||||||||
20.01.2010, 15:01 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Ich verwendete zuerst Derive, inzwischen auch Maple, und zwar mit deinem letzten Code... Und ja, es war genau wie ich es vorhersagte, ohne es vorher ausprobiert zu haben: Die 2. und 3. Zeile gehören vertauscht, um diene Vertauschung von k und l zu kompensieren... Warum machst du so einfache Änderungen nicht einfach, bevor du hier anzuzweifelst, ob sie überhaupt Sinn machen? |
|||||||||||||||||
20.01.2010, 21:04 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Das Vertauschen der 2. und 3. Zeile leuchtet mir nicht ganz ein. Da sind meine Programmierkenntnisse nicht gut genug. Die 2. Zeile ist eine Initialsierung der Variablen und dann geht es in die Schleife und da macht er zu diesen Startwerten alle möglichen Wert l durch. Anschließend erhöht er die Startwerte und macht wieder alle l durch usw. Deshalb verstehe ich diesen Schritt nicht ganz. Auch wenn es nun funktioniert. schönen Gruß |
|||||||||||||||||
20.01.2010, 21:54 | Mystic | Auf diesen Beitrag antworten » | |||||||||||||||
Mann, du bräuchtest echt noch ein bißchen Nachhilfe im Programmieren... Aber vielleicht leuchtet dir ja vielleicht folgendes Argument ein: Wie oft werden in deinem alten bzw. neuen Programm die Anweisungen x:=k; y:=k; durchgeführt? Antwort: Im alten Programm (als 2. Zeile) nur 30 mal, im nun ausgebesserten Programm (als 3.Zeile) aber 900 mal, nämlich als innere Anweisung von 2 Schleifen, da ist also klar ein Unterschied... |
|||||||||||||||||
21.01.2010, 11:59 | Fletcher | Auf diesen Beitrag antworten » | |||||||||||||||
Ach sicher, das Zurücksetzen ist entscheidend! Gruß |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|