Diskreter Logarithmus < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:34 Di 19.04.2011 | | Autor: | Teufel |
| Aufgabe | | Sei [mm] G=\IZ^{\times}_{71}. [/mm] Bestimme [mm] dlog_2(5) [/mm] mod 2. |
Hi!
Weiß jemand, wie ich das machen kann? Davor musste ich folgendes zeigen:
Sei [mm] G=\{1,g,g^2, ...,g^{2m-1}\} [/mm] eine zyklische Gruppe der Ordnung 2m, g ein Erzeuger.
Dann gilt: [mm] $dlog_g(h)=0$ [/mm] mod 2 [mm] \gdw [/mm] J(x)=1, wobei J: $G [mm] \to \{1,g^m\}, [/mm] x [mm] \mapsto x^m$.
[/mm]
Aber ich kann die Aussage ja nicht direkt anwenden, weil 2 kein Erzeuger von [mm] \IZ_{71}^{\times} [/mm] ist. Und eine Untergruppe, die von 2 erzeugt wird, hat 35 Elemente, was nicht gerade ist. Damit kann ich das Bewiesene hier nicht gebrauchen, oder? Aber es wird bestimmt erwartet, dass ich das irgendwie verwerte, weil das die letzte Teilaufgabe einer größeren Aufgabe ist.
Ich habe eben nur mal ein Programm befragt, das mir sagte, dass 2^28=5 ist, also [mm] $dlog_2(5)\equiv [/mm] 0$ mod 2, oder?
Kann mir da bitte jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:53 Di 19.04.2011 | | Autor: | felixf |
Moin Teufel,
> Sei [mm]G=\IZ^{\times}_{71}.[/mm] Bestimme [mm]dlog_2(5)[/mm] mod 2.
>
> Weiß jemand, wie ich das machen kann? Davor musste ich
> folgendes zeigen:
>
> Sei [mm]G=\{1,g,g^2, ...,g^{2m-1}\}[/mm] eine zyklische Gruppe der
> Ordnung 2m, g ein Erzeuger.
>
> Dann gilt: [mm]dlog_g(h)=0[/mm] mod 2 [mm]\gdw[/mm] J(x)=1, wobei J: [mm]G \to \{1,g^m\}, x \mapsto x^m[/mm].
>
> Aber ich kann die Aussage ja nicht direkt anwenden, weil 2
> kein Erzeuger von [mm]\IZ_{71}^{\times}[/mm] ist. Und eine
> Untergruppe, die von 2 erzeugt wird, hat 35 Elemente, was
> nicht gerade ist.
Damit kannst du das Resultat nicht anwenden.
> Damit kann ich das Bewiesene hier nicht
> gebrauchen, oder?
Genau. Und es haengt nun von der Definition von $dlog$ ab, ob die Aufgabe ueberhaupt Sinn macht. Ist das Resultat von $dlog$ eine Restklasse modulo der Ordnung der Basis (hier 2)? Oder ist es die kleinste nicht-negative Zahl $k$ mit [mm] $2^k \eqiuv [/mm] 5 [mm] \pmod{71}$?
[/mm]
Im ersten Fall macht es keinen Sinn, die Restklasse modulo 2 zu betrachten, da 35 ungerade ist. Im zweiten Fall macht es schon Sinn, auch wenn sich die Frage stellt warum man sich das anschauen will.
> Aber es wird bestimmt erwartet, dass ich
> das irgendwie verwerte, weil das die letzte Teilaufgabe
> einer größeren Aufgabe ist.
Ich kann mir vorstellen, dass der Aufgabensteller uebersehen hat, dass 2 kein Erzeuger ist.
> Ich habe eben nur mal ein Programm befragt, das mir sagte,
> dass 2^28=5 ist, also [mm]dlog_2(5)\equiv 0[/mm] mod 2, oder?
Wenn der $dlog$ so definiert ist (als kleinste nicht-negative Zahl), dann ja.
Als "Loesung" kannst du dann einfach [mm] $2^{28} \equiv [/mm] 5 [mm] \pmod{71} \Rightarrow dlog_2 [/mm] 5 = 28 [mm] \equiv [/mm] 0 [mm] \pmod{2}$ [/mm] schreiben 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:09 Di 19.04.2011 | | Autor: | Teufel |
Hi!
Danke für de Antwort erst einmal.
Den diskreten Algorithmus haben wir in der Vorlesung gar nicht definiert (die Aufgabe stammt von einem Kryptographie-Übungsblatt), deshalb habe ich die Wikipedia-Version genommen. Also die, wo der diskrete Logarithmus [mm] dlog_g(h) [/mm] einfach die kleinste, nichtnegative Zahl x ist, sodass [mm] g^x=h [/mm] ist.
Ich glaube auch, dass der Aufgabensteller etwas anderes wollte. Ich habe mal etwas rumgespielt, 7 wäre z.B. ein Erzeuger gewesen.
|
|
|
|
