Seite 1 von 1

Übung 4 e)

Verfasst: 17. Mär 2013 23:07
von AnnaW
Hallo,

ich habe ein Verständnisproblem bei der 4 e)

Wir sollen das Chiffrat (31, 15) entschlüsseln. Damit ist c1 = 31 und c2 = 15, a ist wie gegeben 45

Daraus folgt 15 * 31 ^(-45) = 15 * (31^(-1) ) ^45 soweit komm ich noch mit. Die nächsten Schritte habe ich aus meiner Übungsgruppe, aber ich kann sie nicht mehr nachvollziehen:

= 15 * 44 ^45 = 15 * 31 = 42

Das ganze natürlich modulo 47. Das hab ich jetzt weg gelassen, damit das ganze besser lesbar ist.

Kann mir bitte jemand die letzten beiden Schritte erklären? Ich komm da leider nicht weiter :-(

Viele Grüße

Anna

Re: Übung 4 e)

Verfasst: 18. Mär 2013 03:21
von Ralf
Daraus folgt 15 * 31 ^(-45) = 15 * (31^(-1) ) ^45 soweit komm ich noch mit. Die nächsten Schritte habe ich aus meiner Übungsgruppe, aber ich kann sie nicht mehr nachvollziehen:

= 15 * 44 ^45 = 15 * 31 = 42
Ich glaub dir fehlt nur der Hinweis das das \(c1^{-a} = c1^{-1^{a}}\) ist und das ^-1 nur bedeutet, dass das Inverse in der zyklischen Gruppe gebildet wurde (mit dem erweiterten Euklid).

D.h. der Schritt \(15*31^{-1^{45}}=15*44^{45}\) zeigt nur, dass 44 das Inverse zu 31 ist. Danach wird ganz normal in der Gruppe weitergerechnet.

Klar?

MfG

Re: Übung 4 e)

Verfasst: 18. Mär 2013 11:02
von AnnaW
Vielen Dank :-) Das mit dem Inversen war mir so nicht klar.

Re: Übung 4 e)

Verfasst: 18. Mär 2013 11:16
von GuitarBero
Dazu noch eine Anmerkung:
Das Inverse kann nicht nur durch Euklid, sondern auch durch den Satz von Euler/Fermat berechnet werden:
a^(-1) = a^(phi(n)-1)

Ausfürhlich:
a^(-1) = 1 * a^(-1) = a^phi(n) * a^(-1) = a^(phi(n)-1)

Re: Übung 4 e)

Verfasst: 18. Mär 2013 11:35
von JensWa
es geht auch noch anders :)

c1^(-a) kann man auch schreiben als c1^(phi(p)-a) bzw. c1^(p-1-a)

zumindest habe ich das so gefunden und ich hoffe mal das darf man auch so in der klausur benutzen :)

Re: Übung 4 e)

Verfasst: 18. Mär 2013 17:48
von L4_
Noch präziser:

\(c_1^{-a} \Longleftrightarrow c_1^{k\varphi(n)-a}\), wobei k element aus den ganzen Zahlen ist ;)