diskrete Exponentiation

01.12.2008, 19:46	Andre1	Auf diesen Beitrag antworten »
diskrete Exponentiation Hallo zusammen, Ich bin der Meinung, dass ich entwender in meinem Skript einen Fehler über die diskrete Exponentiation gefunden habe oder gerade auf dem Schlauch stehe. Problem: G sei endliche zyklische Gruppe mit Erzeuger g der Ordnung q. Dann ist die diskrete Exponentiation definiert durch: $\begin{eqnarray} exp_g:\mathbb Z_q\rightarrow G \end{eqnarray}$ $\begin{eqnarray} a\mapsto g^a \end{eqnarray}$ So, jetzt ist die Behauptung, dass die Exponentialfunktion wohldefiniert ist, wegen: $\begin{eqnarray} g^q=1 mod q \end{eqnarray}$ Und an dieser Stelle hänge ich. Beispiel: G ist die multiplikative Gruppe $\begin{eqnarray} \mathbb Z_5^ \end{eqnarray}$ mit Erzeuger $\begin{eqnarray} g=2 \end{eqnarray}$ , also Ordnung $\begin{eqnarray} q=4 \end{eqnarray}$ . Allerdings wwäre dann $\begin{eqnarray} g^q=2^4=16=0 mod 4 \end{eqnarray*}$ Wäre nett, wenn mich jemand aufklären könnte Gruß
01.12.2008, 19:50	kiste	Auf diesen Beitrag antworten »
Warum rechnest du modulo 4, du bist doch in Z_5?!
01.12.2008, 20:03	Andre1	Auf diesen Beitrag antworten »
Hm, aber die Ordnung des Erzeugers ist doch $\begin{eqnarray} q=4 \end{eqnarray}$ ? Ich hab doch also eine Abbildung von $\begin{eqnarray} \mathbb Z_4\rightarrow \mathbb Z_5^ \end{eqnarray*}$ Oder nicht?
01.12.2008, 20:06	kiste	Auf diesen Beitrag antworten »
Ja passt doch auch, $\begin{eqnarray} 2^4 = 16 \equiv 1 \mod 5 \end{eqnarray}$
01.12.2008, 20:08	Andre1	Auf diesen Beitrag antworten »
Ja, aber laut Skript muss ich das mod q also mod 4 rechnen (siehe oben) und genau da liegt irgendwie das problem
01.12.2008, 20:16	kiste	Auf diesen Beitrag antworten »
Dann ist das ganze doch ziemlich schwachsinnig. Eine zyklische Gruppe muss doch nichts mit Zahlen zu tun haben, also kann man doch da gar nicht modulo rechnen. Die Abbildung ist doch eher wohldefiniert da der Erzeuger(also die 1) auf den Erzeuger(also g) geht. Da g^q=1 und davor nicht, sind das eben q verschiedene Elemente, und deshalb wohldefiniert.
Anzeige

01.12.2008, 20:24	Andre1	Auf diesen Beitrag antworten »
Hier mal der Link zum Skript. Es ist sofort die erste Definition 1.1.1 mi.informatik.uni-frankfurt.de/teaching/WS0809/Vorlesung/Kryptographie.pdf
01.12.2008, 20:32	kiste	Auf diesen Beitrag antworten »
Wenn man beides mal mod q wegstreicht macht es Sinn. Ist imo ein Fehler.
01.12.2008, 20:35	Andre1	Auf diesen Beitrag antworten »
kann man das vielleicht noch retten indem man mod q durch etwas anderes ersetzt? Weil oben haben wir ja gesehen, dass es klappt, wenn an in Z5 rechnen würde
01.12.2008, 20:45	kiste	Auf diesen Beitrag antworten »
Ja wir ersetzen es durch $\begin{eqnarray} \varepsilon \end{eqnarray}$ . Dann stimmt es auch.
01.12.2008, 20:49	Andre1	Auf diesen Beitrag antworten »
und was ist bei dir epsilon?
01.12.2008, 20:54	kiste	Auf diesen Beitrag antworten »
Das leere Wort Jetzt wollte ich einmal einen Informatikerwitz machen. Nein ernsthaft: Ist g von Ordnung q so gilt $\begin{eqnarray} g^q = 1 \end{eqnarray}$ und $\begin{eqnarray} g^{k+lq} = g^k \end{eqnarray}$ . Man braucht also überhaupt kein modulo um das zu formulieren.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »