Multiplikatives Inverses berechnen

22.12.2015, 19:21

TheLastOfUs

Auf diesen Beitrag antworten »

Multiplikatives Inverses berechnen

Meine Frage:
Hallihallo,

ich versuche momentan das multiplikative Inverse der Zahl $\begin{eqnarray*} 5^{11} \end{eqnarray*}$ zu berechnen, um später damit eine RSA-Verschlüsselung zu machen.
Das Problem ist für zwei unterschiedliche Methoden bekomme ich zwei unterschiedliche Ergebnisse. Nach dem euklydischen Algorithmus berechne ich folgendes:

Meine Ideen:
$\begin{eqnarray*} 48828125 = 197684 * 257 + 177 \end{eqnarray*}$
$\begin{eqnarray*} 247 = 1 * 177 + 70 \end{eqnarray*}$
$\begin{eqnarray*} 177 = 2 * 70 + 37 \end{eqnarray*}$
$\begin{eqnarray*} 70 = 1 * 37 + 33 \end{eqnarray*}$
$\begin{eqnarray*} 37 = 1 * 33 + 4 \end{eqnarray*}$
$\begin{eqnarray*} 33 = 8 * 4 + 1 \end{eqnarray*}$
$\begin{eqnarray*} 4 = 4 * 1 + 0 \end{eqnarray*}$

$\begin{eqnarray*} 1 = 33 - 8 * 4 \end{eqnarray*}$
$\begin{eqnarray*} = 33 - 8 * (37 - 1 * 33) \end{eqnarray*}$
$\begin{eqnarray*} = 9 * (70 - 1 * 37) - 8 * 37 \end{eqnarray*}$
$\begin{eqnarray*} = 9 * 70 - 17 * 37 \end{eqnarray*}$
$\begin{eqnarray*} = 9 * 70 - 17 * (177 - 2 * 70) \end{eqnarray*}$
$\begin{eqnarray*} = 43 * 70 - 17 * 177 \end{eqnarray*}$
$\begin{eqnarray*} = 43 * (247 - 1 * 177) - 17 * 177 \end{eqnarray*}$
$\begin{eqnarray*} = 43 * 247 - 60 * 177 \end{eqnarray*}$
$\begin{eqnarray*} = 43 * 247 - 60 * (48828125 - 197684 * 247) \end{eqnarray*}$
$\begin{eqnarray*} = 11861040 * 247 - 60 * 48828125 \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow [60]_{247} = [187]_{247} \end{eqnarray*}$

Damit hätte ich normalerweise mein multiplikatives Inverses berechnet. Problem ist: Es stimmt nicht mit der Musterlösung meines Profs überein. Verrechnet habe ich mich nicht, dass habe ich nun sogar schon über verschiedenste Online-Berechnungen geprüft (siehe: http://public.hochschule-trier.de/~knorr/multiplikativesInverse.php für multiplikatives Inverses und http://www.arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm für erweiterten euklydische Algorithmus.)

Also habe ich versucht, es auf eine andere Weise zu ermittlen, nämlich indem ich die Potenzen zerlege und dann die Moduln bild, diese dann miteinander multipliziere und das Endergebnis invertiere. Das sind dann so aus:
$\begin{eqnarray*} [5^{11}]_{247}= [5^4 * 5^4 *5^3] _{247}= [625 * 625 * 125]_[247] = [131 * 131 * 122]^{-1} _{247} = [2093642]^{-1} _{247} = [70]^{-1} _{247} \end{eqnarray*}$

Und die 70 wäre hier tatsächlich auch die Lösung, die mein Prof in seinen Musterlösungen verzeichnet. Jetzt bin ich etwas verunsichert. Habe irgendetwas beim euklydischen Algorithmus übersehen oder warum liefert dieser ein anscheinend falsches Ergebnis? :?
Wäre sehr glücklich über jegliche Hilfe. Auch wenn ich weiß, dass meine Rechnungen endlos erscheinen. Gott

Gott

22.12.2015, 19:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von TheLastOfUs
ich versuche momentan das multiplikative Inverse der Zahl $\begin{eqnarray*} 5^{11} \end{eqnarray*}$ zu berechnen, um später damit eine RSA-Verschlüsselung zu machen.

Es wäre sicher hilfreich, wenn du das verwendete Modul ( =247 verwirrt

verwirrt

) gleich in der Aufgabenstellung nennst, statt dass man es aus dem Gewusel deiner Gleichungsketten erst enträtseln muss. unglücklich

unglücklich

22.12.2015, 19:39

TheLastOfUs

Auf diesen Beitrag antworten »

Ach Schreck, ja natürlich! Modul 247! Und in der ob ersten Zeile meines euklydischen Algorithmus habe ich mich natürlich auch gleich vertippt. Es muss * 247 heißen und nicht * 257! Hammer

Hammer

Bei dem ganzen Text kann schon mal schnell was vergessen werden oder falsch geraten.

22.12.2015, 19:49

HAL 9000

Auf diesen Beitrag antworten »

$\begin{align*} 5^{-11} \equiv 187\bmod 247 \end{align*}$ ist richtig.

Zitat:

Original von TheLastOfUs
$\begin{eqnarray*} \rightarrow [60]_{247} = [187]_{247} \end{eqnarray*}$

Das ist natürlich Unfug - richtig wäre $\begin{align*} 187\equiv -60\bmod 247 \end{align*}$ . d.h. da fehlt bei dir ein Minuszeichen.

Zitat:

Original von TheLastOfUs
$\begin{eqnarray*} [5^{11}]_{247}= [5^4 * 5^4 *5^3] _{247}= [625 * 625 * 125]_[247] = [131 * 131 * {\color{red}122}]^{-1} _{247} = [2093642]^{-1} _{247} = [70]^{-1} _{247} \end{eqnarray*}$

Erneut so ein Vorzeichenfehler: Es ist nicht $\begin{align*} 125\equiv 122\bmod 247 \end{align*}$ , sondern $\begin{align*} 125\equiv -122\bmod 247 \end{align*}$ . unglücklich

unglücklich

Es hat ganz den Anschein, als ob du Vorzeichen nach Belieben weglässt, und du dir dadurch diese ganzen scheinbaren Widersprüche einhandelst. Wenn du das abstellst, dann verschwinden auch diese Probleme.

22.12.2015, 19:59

TheLastOfUs

Auf diesen Beitrag antworten »

Natürlich, das Minus! Hammer

Hammer

Aber ist denn die zweite Version absolut falsch und es nur Zufall, dass ich auf die 70 komme? Denn wie gesagt, ich möchte ja nicht behaupten, dass mein Prof unfehlbar ist, aber er hat genau $\begin{eqnarray*} [-70]_{247} = [177]_{247} \end{eqnarray*}$ heraus. :?

22.12.2015, 20:02

TheLastOfUs

Auf diesen Beitrag antworten »

Ah okay, damit hätte sich diese Frage auch erledigt. Also scheinbar tatsächlich ein Fehler seitens des Profs.
Vielen Dank jedenfalls für die zackige Hilfe! Gott

Gott

Anzeige

22.12.2015, 20:10

TheLastOfUs

Auf diesen Beitrag antworten »

Aber selbst wenn ich es nun mit der -122 berechne, so komme ich wieder auf mein $\begin{eqnarray*} [-70]_{247} = [177]_{247} \end{eqnarray*}$ unglücklich

unglücklich

22.12.2015, 20:19

URL

Auf diesen Beitrag antworten »

Woher kommt hier

Zitat:

$\begin{eqnarray*} [5^{11}]_{247}= [5^4 * 5^4 *5^3] _{247}= [625 * 625 * 125]_[247] = [131 * 131 * 122]^{-1} _{247} = [2093642]^{-1} _{247} = [70]^{-1} _{247} \end{eqnarray*}$

eigentlich auf einmal der Exponent -1 ?

22.12.2015, 20:41

TheLastOfUs

Auf diesen Beitrag antworten »

Ist ebenfalls falsch. Das soll eigentlich nur mein Rest sein. Kein Inverses oder irgendwas. unglücklich

unglücklich

Das Inverse wäre ja nur 187 bzw 177.

22.12.2015, 21:04

URL

Auf diesen Beitrag antworten »

Hab bitte Geduld mit mir, ich verstehe noch immer nicht, was du eigentlich machen willst.
Dein Modul ist n=247=13*19. Solltest du jetzt nicht zwei Zahlen finden, die bzgl. $\begin{eqnarray*} \varphi(n)=12\cdot 18=216 \end{eqnarray*}$ zueinander invers sind?

22.12.2015, 21:17

TheLastOfUs

Auf diesen Beitrag antworten »

Haha

Big Laugh

Ich glaube doch eher mir gegenüber muss man Geduld zeigen.
Zwei Zahlen? Ich meine, deine Zerlegung in Primzahlen und die Berechnung des phi's ist mir auch bekannt, aber ich bin mir nicht sicher, was ich damit in meiner Berechnung anfangen soll. Ich versuche eigentlich nur meine Restlasse für $\begin{eqnarray*} 5^{11} (mod 247) \end{eqnarray*}$ zu ermitteln.
Das habe ich einmal über den euklydischen Algorithmus versucht und einmal über die Zerlegung von Potenzen.

22.12.2015, 21:35

URL

Auf diesen Beitrag antworten »

Eingangs ging es doch um

Zitat:

multiplikative Inverse der Zahl $\begin{eqnarray*} 5^{11} \end{eqnarray*}$ zu berechnen

verwirrt

Das ist doch etwas völlig anderes als

Zitat:

Restlasse für $\begin{eqnarray*} 5^{11} (mod 247) \end{eqnarray*}$ zu ermitteln

Wenn es nur um die Restklasse geht, hat dein Prof völlig recht $\begin{eqnarray*} 5^{11}\equiv 177 \bmod 247 \end{eqnarray*}$
Ich sehe jetzt nicht, wie man diese Aufgabe mit dem (erweiterten) euklidischen Algorithmus lösen sollte verwirrt

verwirrt

Edit: Ach ja, auf $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ kam ich, weil du RSA erwähntest.

22.12.2015, 21:48

TheLastOfUs

Auf diesen Beitrag antworten »

Habe ich vielleicht irgendwo einen Denkfehler. Am besten ich schreibe hier einfach einmal die Aufgabe nieder (habe das anfangs lieber gelassen, weil RSA ja eher ein Thema aus der Informatik ist als eines aus der Mathematik). Also folgendes:
Die Nachricht 5 soll mit dem RSA-Verfaren verschlüsselt werden. Der öffentliche Schlüssel lautet (11, 247), der private (59, 247). Wie lautet die verschlüsselte Nachricht? Entschlüsseln Sie zur Probe die verschlüsselte Nachricht.

Also kann ich meine Restklasse ermitteln wie ich das gedacht habe (mal ganz vereinfacht aufgeschrieben):
$\begin{eqnarray*} 5^{11} = 5^4 * 5^4 * 5^3 = 625 * 625 * 125 = 131 * 131 * (-122) = -2093642 \end{eqnarray*}$
und nun
$\begin{eqnarray*} [-2093642] \end{eqnarray*}$ (mod 247) $\begin{eqnarray*} = [177]_{247} \end{eqnarray*}$ oder gibt es da einen viel besseren Weg?

Und während ich das hier schreibe bemerke ich selbst schon: Was habe ich da eigentlich mit dem euklydischen Algorithmus gemacht? Der berechnet doch nur das ggT und die Inverse... und warum wollte ich überhaupt die Inverse haben. Auweia... irgendwas ist da in meinem Kopf ganz schrecklich durcheinander geraten. Hammer

Hammer

22.12.2015, 22:00

URL

Auf diesen Beitrag antworten »

Ja, sieht ganz danach aus LOL Hammer

LOL Hammer

22.12.2015, 22:13

TheLastOfUs

Auf diesen Beitrag antworten »

Okay, also die Methode wie ich die Restklasse ermittelt habe, ist also in Ordnung?

Und wenn ich nun die Nachricht wieder entschlüsseln möchte, dann müsste ich dieses Mal $\begin{eqnarray*} 177^{59} \end{eqnarray*}$ (mod 247) rechnen, oder? Denn das versuche ich gerade, aber nun komme ich nicht mehr auf 5 zurück. Ich habe $\begin{eqnarray*} 177^{59} \end{eqnarray*}$ zerteilt in $\begin{eqnarray*} 177^{10*5+9} (mod\,\,m)=(177^{10})^5*177^9(mod\,\,m) \end{eqnarray*}$ aber ich komme nicht zurück auf meine 5! traurig

traurig

22.12.2015, 22:42

URL

Auf diesen Beitrag antworten »

Ich hätte zuerst noch $\begin{eqnarray*} 131^2 \bmod 247 \end{eqnarray*}$ berechnet, aber das macht keinen wesentlichen Unterschied.

Wenn du die Zerlegung von 247 im Primfaktoren benutzen darfst, dann geht das mit dem Chinesischen Restsatz am schnellsten. Das ist übrigens der Grund, warum es sinnvoll sein kann, die Primfaktoren auch nach Berechnung des Moduls zu speichern.

Edit: Allem Anschein nach ist es für den direkten Weg geschickter $\begin{eqnarray*} (-70)^{59}\bmod 247 \end{eqnarray*}$ zu rechnen.
Ich würde dann mit $\begin{eqnarray*} 10^3\equiv 12 \end{eqnarray*}$ und $\begin{eqnarray*} 12^3\equiv -1 \end{eqnarray*}$ weiter machen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »