Faktorisierung - Pollards rho-Method

Neue Frage »

Fletcher Auf diesen Beitrag antworten »
Faktorisierung - Pollards rho-Method
Guten Tag,

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?

code:
1:
N:= 10243189921255363578958702669327317711144173434989191540873992161251123635826218828997305156865278990013053915626354016579656085077846515168174544041859115547902528567131096788107114462543800336264133


code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
for l from 2 to 30 do 
x[1] := l; y[1] := l; 
for k from 2 to 30 do 
for i from 2 to 8 do 
x[i] := `mod`(x[i-1]^2+k, N); 
y[i] := `mod`(y[i-1]^2+k, N);
y[i] := `mod`(y[i]^2+k, N); 
print(l, k, igcd(x[i]-y[i], N)) 
end do 
end do 
end do


Gruß
Mystic Auf diesen Beitrag antworten »
RE: Faktorisierung - Pollards rho-Method
Zitat:
Original von Fletcher
Wo liegt mein Fehler?


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

Zitat:
Original von Fletcher
Na gut l und k könnte ich auch bei 1 beginnen lassen.


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... unglücklich

Zitat:
Original von Fletcher
Warum sollte es nicht mit arrays funktionieren? Ist doch kein großer Fehler, außer das ich mehr Speicher brauche!


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...

Zitat:
Original von Fletcher
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


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

Danke!
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:


code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
for k to 30 do 
x := k; y := k; 
for l to 30 do 
for j to 50 do 
x := `mod`(x^2+l, N2); y := `mod`(y^2+l, N2); y := `mod`(y^2+l, N2); d := igcd(x-y, N2); 
if d > 1 then print(k, l, j, d) end if 
end do 
end do 
end do


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?


code:
1:
2:
3:
4:
N2:=26002291563094847186576412727063100863136369364659756976331218730803348576558809
23594688308365896773610971726405071891569067622660848014956785627651626756797549
26267172313936344445543985803748172357042957438219666733506083327673902179540095
019265061869081394255754110504231009



code:
1:
2:
3:
4:
33765706093572807492952015105350169627151460252420338955276106325298125064337767
16158841933423175151749897670804625328049245964004161664864239917810204209997154
17946366288652598127253708132370699686842788234943894913317698489580860037487536
05868320927273795360489288881679004653


Schönen Gruß
 
 
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)...
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ß
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... unglücklich
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
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Fletcher
Mich würde interessieren wie du auf die k's und l's gekommen bist und mein Programm nicht funktioniert und bei N1 schon


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...
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ß
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Fletcher
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ß


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? verwirrt
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ß
Mystic Auf diesen Beitrag antworten »

Mann, du bräuchtest echt noch ein bißchen Nachhilfe im Programmieren... Big Laugh

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... Augenzwinkern
Fletcher Auf diesen Beitrag antworten »

Ach sicher, das Zurücksetzen ist entscheidend! Freude

Gruß Wink
Neue Frage »
Antworten »



Verwandte Themen

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