Übung 4 e)

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Übung 4 e)

Beitrag von AnnaW » 17. Mär 2013 23:07

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

Ralf
Erstie
Erstie
Beiträge: 11
Registriert: 7. Sep 2010 18:32

Re: Übung 4 e)

Beitrag von Ralf » 18. Mär 2013 03:21

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

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Übung 4 e)

Beitrag von AnnaW » 18. Mär 2013 11:02

Vielen Dank :-) Das mit dem Inversen war mir so nicht klar.

GuitarBero
Neuling
Neuling
Beiträge: 10
Registriert: 27. Feb 2013 18:57

Re: Übung 4 e)

Beitrag von GuitarBero » 18. Mär 2013 11:16

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)

JensWa
Neuling
Neuling
Beiträge: 5
Registriert: 25. Mai 2011 14:16

Re: Übung 4 e)

Beitrag von JensWa » 18. Mär 2013 11:35

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 :)

L4_
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 104
Registriert: 24. Apr 2012 15:44

Re: Übung 4 e)

Beitrag von L4_ » 18. Mär 2013 17:48

Noch präziser:

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

Antworten

Zurück zu „Archiv“