Erweiterter Euklidischer Algo. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:03 Di 17.02.2009 | | Autor: | n2x |
| Aufgabe | Ermittelung alle multiplikativ inverse Elemente.
(b = a^-1 mod m ) |
Guten Abend,
ich versuche mir den erweiterten euklidischen Algorithmus beizubringen.
Um zu überprüfen ob meine Ergebnisse die ich ausgerechnet habe richtig sind, verwende ich eine Seite die den Algorithmus in Zusammenhang mit einer RSA-Verschluesselung benutzt.
Flash-Tool: Link:
http://www.mathe-online.at/materialien/Franz.Embacher/files/RSA/
Wenn ich die Primzahlen p=5 und q=23 wähle, berechne ich erstmal
n durch pq -> 115. Danach m durch (p-1)*(q-1) -> 88.
Als teilerfremde Zahl zu m habe ich einfach mal 5 gewählt.
Meine geheime Zahl ist dabei ja völlig belanglos, gewählt habe ich jedenfalls 66 und mit der Verschlüsselung 56 als y rausbekommen.
Jetzt kommts zur Anwendung des erweiterten euklidischen Algorithmus:
p=5; q=23
23 = 4 * 5 + 3
5 = 1 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0
ggT(5;23) -> 1
1 = 3 - 1 * 2
1 = 3 - 1 * (5 - 3)
1 = 3 - 1*5 + 1*3
1 = - 1*5 + 2*3
1 = 2*(23-4*5) - 1*5
1 = 2*23 - 8*5 - 1*5
1 = 2*23 - 9*5
=> -9*5 mod 23 = 1 (-9 positiv machen)
=> 14*5 mod 23 = 1
Ich bin davon ausgegangen, dass das richtig ist, dem ist aber nicht so. Das Tools sagt mir, wenn ich die 14 als b eingebe, dass ich mich wohl verrechnet habe. Ganze 3 Stunden sitze ich vor dieser vermeintlich einfachen Aufgabe und frage mich wo mein Fehler steckt.
Durch ausprobieren bin ich darauf gekommen das b = 53 ist - nur wieso?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hoffnungslose Grüße n2x.
|
|
| |
|
Hallo n2x,
auch wenn Du hier schon ein halbes Jahr registriert bist: ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Immerhin ist es ja erst Deine zweite Anfrage hier.
Diese hier verstehe ich allerdings nicht, obwohl mir das Themengebiet vertraut ist. Deine Rechnungen stimmen, aber ich sehe nicht, worauf Du hinaus willst. Geht es Dir um den RSA-Algorithmus und das public-key-Verfahren? Warum wählst Du dann m als [mm] (p_1-1)*(p_2-1) [/mm] und nicht als [mm] p_1*p_2? [/mm] Das kann nicht klappen.
Leg also noch etwas mehr Information nach, sonst ist Deine Anfrage nicht zu decodieren. 
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:38 Mi 18.02.2009 | | Autor: | n2x |
Guten Abend.
Jetzt nach längerem überlegen ist mir der Fehler aufgefallen, so zB. dass ich bei dem normalen euklidische Algorithmus anstatt beide Primzahlen, m und eine Primzahl wählen muss.
m habe ich als (p-1)*(q-1) definiert, da dieses nichts anderes als PHI n ist.
n wird dabei durch p*q errechnet.
Vielen Dank.
n2x
|
|
|
|
