Erweiteter Euklidscher Algorithmus |
| 20.07.2008, 15:29 | Meisenmann | Auf diesen Beitrag antworten » | ||
| Erweiteter Euklidscher Algorithmus ich wollte gerade den erweiterten Euklidischen Algorithmus einsetzen, aber irgendwie stimmt das Ergebnis nicht: Für 60 und 13 so dass gilt u*13 - v*60 = 1 Dazu habe ich zunächst den ggT(60, 13) berechnet 60 = 4 * 13 + 8 13 = 1 * 8 + 5 8 = 1 * 5 + 3 5 = 1 * 3 + 2 3 = 1 * 2 + 1 2 = 2 * 1 + 0 und dann dadurch den erweiterten Euklidischen Algorithmus: 1= 3 – 1 * 2 1 = 3 – 1 * (5-1*3) => 2 * 3 – 5 1 = 2 * (8-1*5) – 5 => 2 * 8 – 3 * 5 1 = 2 * 8 – 3 * (13-1*8) => 5 * 8 – 3 * 13 1 = 5 * (60 - 4*13) – 3 * 13 => 5 * 60 – 23 * 13 Was hab ich da bitte falsch gemacht -> das Ergebnis erfüllt nicht die Vorgaben. Lg Meisenmann |
||||
| 20.07.2008, 15:37 | 42 | Auf diesen Beitrag antworten » | ||
Moin, was stimmt denn nicht? ggt(13, 60) = 1 = -23*13+5*60 Passt doch alles wunderbar. |
||||
| 20.07.2008, 15:38 | Zizou66 | Auf diesen Beitrag antworten » | ||
Wo genau liegt jetzt dein Problem? Edit: Zu späät.... |
||||
| 20.07.2008, 16:11 | Meisenmann | Auf diesen Beitrag antworten » | ||
Hi, ich möchte das Ganze für RSA einsetzen um den privaten Schlüssel d zu berechnen (nur probeweise für kleine schlüssel) Dazu habe ich ein n und ein e -> n berechnet sich aus p*q Phi(n) = (p-1)*(q-1) und es soll gelten e*d mod phi(n)=1 Nun zu dem Beispiel: n=143 -> p=13, q=11 -> phi(n)=120 Nun soll ich d berechnen -> so das gilt 13*d mod 120 = 1 Dazu habe ich den euklidischen Algortihmus eingesetzt, aber das ergebnis stimmt nicht mit der Bedingung überein: 13*23 mod 120 = 1 Was mach ich dann falsch? Lg Meisenmann |
||||
| 20.07.2008, 16:16 | kiste | Auf diesen Beitrag antworten » | ||
warum berechnest du dann ggt(13,60) und nicht ggt(13,120)? |
||||
| 20.07.2008, 16:55 | Meisenmann | Auf diesen Beitrag antworten » | ||
Das ist eine durchaus berechtigte frage 
Sorry, mein Fehler, von zuviel rechnen heuteAber mit folgenden Zahlen bekomm ich das nicht hin: n = 143 ; e = 17 -> P= 11, q=13 ; Æ(n) = 120 -> 17*d mod 120 = 1 Ggt(120, 17) 120 = 7 * 17 + 1 17 = 17 * 1 + 0 ggT(120, 17) = 1 -> Erweiterter Euklidischer Algorithmus: 1 = 120 -7 * 17 D = 7 / e=17, aber 7*17 mod 120 ist nicht 1 Was hab ich jetzt wieder falsch gemacht? Lg Meisenmann |
||||
| Anzeige | ||||
|
|
||||
| 20.07.2008, 17:14 | Meisenmann | Auf diesen Beitrag antworten » | ||
Und noch zu meinem Vorherigen Post mit 120 möchte ich es ja nicht rechnen, sondern schon mit 60, so das gilt 13 * d mod 60 = 1. Lg |
||||
| 20.07.2008, 18:05 | kiste | Auf diesen Beitrag antworten » | ||
Nein aber -7*17 mod 120 = 1 ebenfalls vorhin(warum auch immer du mod 60 haben willst): -13*23 mod 60 = 1 |
||||
| 22.07.2008, 10:54 | Meisenmann | Auf diesen Beitrag antworten » | ||
Hi, danke nochmals! Lg Meisenmann |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
