Diskrete Logarithmen in Z/nZ, n natürlich!?

01.04.2011, 09:45

Frobenius

Diskrete Logarithmen in Z/nZ, n natürlich!?

Meine Frage:
Diskrete Logarithmen werden -- wo immer ich in der Kryptoliteratur schaue -- über primen Restklassengruppen definiert.
Warum genügt nicht eine zyklische Gruppe mit großer Ordnung? Also zum Beispiel auch Z/nZ, falls es einen Erzeuger darin gibt?

Meine Ideen:
In einer zyklischen Gruppe mit großer Ordnung sind diskrete Logarithmen doch fast immer (meist multiplikative Gruppen) schwer zu lösen.
Oder habe ich etwas übersehen?

01.04.2011, 11:11

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Frobenius
Warum genügt nicht eine zyklische Gruppe mit großer Ordnung?

"Genügen" wofür? verwirrt

Du musst schon ein bisschen konkreter werden als nur mit der vagen Erwähnung von Krypto.

01.04.2011, 16:12

Mystic

Auf diesen Beitrag antworten »

RE: Diskrete Logarithmen in Z/nZ, n natürlich!?

Zitat:

Original von Frobenius
Meine Ideen:
In einer zyklischen Gruppe mit großer Ordnung sind diskrete Logarithmen doch fast immer (meist multiplikative Gruppen) schwer zu lösen.
Oder habe ich etwas übersehen?

Ja, du hast übersehen, dass genau diese Tatsache ohnehin verwendet wird... Beim klassischen ElGamal-Verfahren wird u.a. die prime Restklassengruppe mod p verwendet, wo p eine große Primzahl (mit mindestens 1024 Bits in Binärschreibweise) ist... Diese Gruppe ist bekanntlich auch immer zyklisch...

03.04.2011, 20:59

Frobenius

Auf diesen Beitrag antworten »

"Genügen" meine ich im Sinne von, es gibt Anwendungen, in denen es Sinn macht, den diskreten Logarithmus auf (Z/nZ, *) zu definieren.

Allerdings bin ich mittlerweile soweit, dass es glaube ich keinen Erzeuger multiplikativer Halbgruppen der Art Z/nZ={0,1,...,n-1} gibt. Ist dem so?

03.04.2011, 23:23

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Frobenius
Allerdings bin ich mittlerweile soweit, dass es glaube ich keinen Erzeuger multiplikativer Halbgruppen der Art Z/nZ={0,1,...,n-1} gibt. Ist dem so?

Hm, habe ich nicht oben schon gesagt, dass es im Fall, dass n prim ist, sehr wohl einen Erzeuger gibt... Allgemeiner hat diese Gruppe genau dann einen Erzeuger, wenn n=1,2,4, $\begin{eqnarray*} p^e,2p^e \end{eqnarray*}$ (p ungerade Primzahl, e>0) ist...

03.04.2011, 23:35

Frobenius

Auf diesen Beitrag antworten »

Mist, jetzt habe ich den Erzeuger 5 der Halbgruppe (Z/12Z,*)\0 = {1,2,3,4,5,6,7,8,9,10,11} = <5> gefunden. Es ist doch dann im Allgemeinen nicht falsch zu sagen, der diskrete Log mod 12 zur Basis 5 ist die kleinste natürliche Zahl, für die gilt: y=5^x mod 12.
Meine Frage also: Warum definiert die Literatur den diskreten Logarithmus in Einheitengruppen? Welchen Vorteil liefert die Existenz der multiplikativ Inversen?

03.04.2011, 23:40

Frobenius

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

Zitat:

Original von Frobenius
Allerdings bin ich mittlerweile soweit, dass es glaube ich keinen Erzeuger multiplikativer Halbgruppen der Art Z/nZ={0,1,...,n-1} gibt. Ist dem so?

Das habe ich verstanden. Aber es lässt sich doch auch wunderbar in Restklassenhalbgruppen rechnen (falls man das so sagen kann), die nicht zwangsläufig prim sind. Siehe (Z/12Z,*)\{0}

03.04.2011, 23:44

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Frobenius
Mist, jetzt habe ich den Erzeuger 5 der Halbgruppe (Z/12Z,*)\0 = {1,2,3,4,5,6,7,8,9,10,11} = <5> gefunden. Es ist doch dann im Allgemeinen nicht falsch zu sagen, der diskrete Log mod 12 zur Basis 5 ist die kleinste natürliche Zahl, für die gilt: y=5^x mod 12.
Meine Frage also: Warum definiert die Literatur den diskreten Logarithmus in Einheitengruppen? Welchen Vorteil liefert die Existenz der multiplikativ Inversen?

Langsam geb ich's wirklich auf mit dir... Du ignorierst beharrlich einfach alles was ich zu dem Thema schreibe und behauptest immer glatt das Gegenteil... unglücklich

Habe ich dir nicht oben alle n angegeben, für welche es einen Erzeuger in der primen Restklassengruppe mod n gibt? Ja... Und ist 12 dabei? Nein... Also gibt es mod 12 keinen Erzeuger und schon gar nicht ist 5 einer, denn es ist ja bereits

$\begin{eqnarray*} 5^2 =25 \equiv 1 \mod 12 \end{eqnarray*}$

Die Potenzen von 5 mod 12 sind also 5,1,5,1,5,1,... Keine Spur also von einem Erzeuger... geschockt

Edit: Überhaupt hat die prime Restklassengruppe mod 12 nur die Resttklassen von 1,5,7 und 11 als Elemente, also ganze 4 Stück!!!

04.04.2011, 00:08

Frobenius

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

Zitat:

Langsam geb ich's wirklich auf mit dir... Du ignorierst beharrlich einfach alles was ich zu dem Thema schreibe und behauptest immer glatt das Gegenteil... unglücklich

Ich glaube wir reden an einander vorbei. Ich habe dummerweise den Erzeuger 5 der Gruppe (Z/12Z, +) betrachtet nicht der multiplikativ geschriebenen Gruppe (Z/12Z, *).
Mit "an einander vorbei" meine ich, dass ich NICHT von primen Restklassen modulo n spreche, sondern von der multiplikativ geschriebenen Halbgruppe (es existiert also nicht zwingend ein Inverses) (Z/nZ, *)\{0}.

Zitat:

Original von Mystic
Allgemeiner hat diese Gruppe genau dann einen Erzeuger, wenn n=1,2,4, $\begin{eqnarray*} p^e,2p^e \end{eqnarray*}$ (p ungerade Primzahl, e>0) ist...

So wie ich dich jetzt verstanden habe, gibt es keinen multiplikativen Erzeuger einer Halb(!)gruppe der Form {1,2,...,n-1}=(Z/nZ,*)\{0}, falls n nicht die von dir angesprochene Form hat.

Zitat:

Original von Mystic
Langsam geb ich's wirklich auf mit dir... Du ignorierst beharrlich einfach alles was ich zu dem Thema schreibe und behauptest immer glatt das Gegenteil... unglücklich

Bitte noch nicht aufgeben! smile

04.04.2011, 00:51

Frobenius

Auf diesen Beitrag antworten »

Puh... Nochmal eine Idee, vielleicht habe ich jetzt die eigentlich erhoffte Antwort:

Jede multiplikativ geschriebene zyklische Halbgruppe der Form $\begin{eqnarray*} G=(\mathbb{Z}/n\mathbb{Z},\cdot)\backslash\{0\} \end{eqnarray*}$ ist eine prime Restklassengruppe. Denn, zyklisch heißt es gibt einen Erzeuger g für den $\begin{eqnarray*} g^{ord(G)}\bmod n\equiv 1\bmod n \end{eqnarray*}$ gilt. Doch dann gibt es zu jedem Element $\begin{eqnarray*} a\in <g> \end{eqnarray*}$ ein Inverses $\begin{eqnarray*} a^{-1} \end{eqnarray*}$ , da $\begin{eqnarray*} a\bmod n\equiv g^k\bmod n \end{eqnarray*}$ und wegen $\begin{eqnarray*} g^kg^{ord(G)-k}\bmod n\equiv g^{Ord(G)}\bmod n \end{eqnarray*}$ ist $\begin{eqnarray*} g^{Ord(G)-k}\bmod n \end{eqnarray*}$ das zu $\begin{eqnarray*} a\bmod n \end{eqnarray*}$ Inverse. Damit ist $\begin{eqnarray*} G \end{eqnarray*}$ eine Einheitengruppe und deshalb $\begin{eqnarray*} n \end{eqnarray*}$ prim. Also macht es eben KEINEN Sinn, den diskreten Logarithmus anders als modulo einer Primzahl zu definieren, falls man als Gruppenoperation die Multiplikation betrachtet. Ist die Gruppenoperation die Addition, so ist n nicht unbedingt prim zu wählen, da es in $\begin{eqnarray*} (\mathbb{Z}/n\mathbb{Z},+) \end{eqnarray*}$ für jedes natrüliche n einen Erzeuger gibt.

Falls mir jemand diese Annahme verbessern oder bestätigen kann, bin ich ihm dafür sehr dankbar.

04.04.2011, 06:57

Mystic

Auf diesen Beitrag antworten »

OK, langsam, langsam beginne ich zu begreifen, insbesondere dass ich offenbar zuviel an Zahlentheoriekenntnissen bei dir vorausgesetzt habe...

Zunächst einmal ist es richtig, dass aus

$\begin{eqnarray*} a^k \equiv 1 \mod n \end{eqnarray*}$

automatisch folgt, dass ggT(a,n)=1, d.h., 1 kann mod n nur dann als Potenz von a dargestellt werden, wenn a relativ prim ist zu n und diese notwendige Bedingung ist, wie man zeigen kann, dann auch schon hinreichend... Insbesondere ist

$\begin{eqnarray*} (\mathbb{Z}/n\mathbb{Z}\setminus\{0\},*) \end{eqnarray*}$

genau dann eine Gruppe, wenn n eine Primzahl ist... Man beachte, dass im Fall, dass n nicht prim ist, also in nichttrivialer Weise als Produkt n=rs schreibbar ist, ja gilt

$\begin{eqnarray*} rs \equiv 0 \mod n \end{eqnarray*}$

d.h., es liegt nicht einmal eine binäre Operation vor!

Neue Frage »

Antworten »

Diskrete Logarithmen in Z/nZ, n natürlich!?

Verwandte Themen