Potenzregeln in Restklassengruppen

Moderator: Einführung in die Kryptographie

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Potenzregeln in Restklassengruppen

Beitrag von arne.lottmann » 9. Feb 2013 11:43

\((\mathbb{Z}/_{7\mathbb{Z}})^*\)
\((3)^{-3} \mathop{\equiv}\limits^{?} (3^{-1})^3\)
\((3)^{-3} \equiv 3^4 \equiv 81 \equiv 4\;mod\;7\)
\(3^{-1} \equiv 5\;mod\;7;\, 5^3 \equiv 125 \equiv 6\;mod\;7\)

Ist mir gerade beim Betrachten des Babystep-Giantstep-Algorithmus aufgefallen (stark vereinfacht). Dort wird \(\gamma^{-r} \equiv (\gamma^{-1})^r\) benutzt, was nach obigem Beispiel nicht allgemein gilt. Nach gewöhnlichen Potenzregeln würde ich der Umformung zustimmen, aber anscheinend gelten diese nicht in Restklassengruppen. Oder mache ich einen ganz dummen Fehler?

//EDIT: (Zwei Minuten später…) Liegt es daran, dass man in der Gruppe die Addition nicht kennt und deswegen \(-3 \equiv 4\) gar nicht feststellen kann? Dann hätte man ja gar keine anderen Möglichkeit, \(3^{-3}\) zu schreiben als \((3^{-1})^3\).

Anmerkung: \(3^5 \equiv 243 \equiv 33 \equiv 5\;mod\;7.\) Nur falls jemand auf die Idee kommt, man solle das multiplikativ Inverse statt dem additiv Inversen nehmen.

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Potenzregeln in Restklassengruppen

Beitrag von ISTler » 9. Feb 2013 12:14

Ich glaube es verhält sich folgendermaßen:
In den Potenzen rechnest du modulo der Elementordnung. Die Elementordnung kennst du im Allgemeinen nicht, weist aber, dass sie die Gruppenordnung teil. Daher rechnet man in den Potenzen meistens modulo der Gruppenordnung.

In deinem Beispiel ist:
\(-3 \mathop{\equiv} 3\; mod\; \varphi(7)\) und daher:
\((3)^{-3} \equiv 3^3 \equiv 27 \equiv 6 \;mod\;7\)

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Potenzregeln in Restklassengruppen

Beitrag von arne.lottmann » 9. Feb 2013 13:19

Okay… hast du eventuell auch eine Quelle, um das "glaube ich" zu stützen?

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Potenzregeln in Restklassengruppen

Beitrag von ISTler » 9. Feb 2013 13:35

Schau dir mal Theorem 3.9.2 und Korollar 3.9.3 aus Buchmanns Buch an. Da solltest du auch einen Beweis finden.

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Potenzregeln in Restklassengruppen

Beitrag von arne.lottmann » 9. Feb 2013 14:03

Okay, danke. Hab's verstanden.

Antworten

Zurück zu „Einführung in die Kryptographie“