Diskreter Logarithmus < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:10 Sa 30.07.2011 | | Autor: | Hanz |
Hi,
ich verstehe gerade eine Sache nicht und zwar kann man die diskrete Logarithmusfunktion doch als Umkehrabbildung der diskreten Exponentiation betrachten, oder?
Bei wikipeida: http://de.wikipedia.org/wiki/Diskreter_Logarithmus
Hier ist mir die Definition und die Schreibweise der exp und log Funktionen klar.
Nun habe ich aber versucht in diesem Dokument auf der ersten Seite
http://www.staff.uni-mainz.de/pommeren/Kryptologie/Asymmetrisch/4_DiskrLog/diskrlog.pdf
dieses Diagramm nachzuvollziehen... warum definieren die da die exp-Funktion von [mm] \IZ \to [/mm] G und die log-Funktion dann von <a> [mm] \to \IZ_s?
[/mm]
Ist die Exponentialfunktion hier dann überhaupt die direkte Umkehrfunktion?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:06 Sa 30.07.2011 | | Autor: | felixf |
Moin,
> ich verstehe gerade eine Sache nicht und zwar kann man die
> diskrete Logarithmusfunktion doch als Umkehrabbildung der
> diskreten Exponentiation betrachten, oder?
ja, mit genau den gleichen Einschraenkungen wie beim "echten" Logarithmus.
Wenn du [mm] $\exp [/mm] : [mm] (\IC, [/mm] +) [mm] \to (\IC^\ast, \cdot)$ [/mm] betrachtest, ist diese Funktion nicht injektiv. (Der Kern ist $2 [mm] \pi [/mm] i [mm] \IZ$.) [/mm] Dementsprechend gibt es keine "richtige" Umkehrfunktion. Man kann das immer nur "lokal schoen" machen.
Wenn man jetzt allerdings den Homomorphiesatz benutzt, so erhaelt man ja einen (surjektiven) Homomorphismus $h : [mm] \IC [/mm] / 2 [mm] \pi [/mm] i [mm] \IZ \to \IC^\ast$ [/mm] mit $h(z + 2 [mm] \pi [/mm] i [mm] \IZ) [/mm] = [mm] \exp(z)$. [/mm] Dieser ist nach dem Homomorphiesatz bijektiv, womit er eine Umkehrfunktion hat -- den Logarithmus! Diesen kann man also als Funktion [mm] $\IC^\ast \to \IC [/mm] / 2 [mm] \pi [/mm] i [mm] \IZ$ [/mm] auffassen: der Wert [mm] $\log(z)$ [/mm] ist halt nur bis auf ganzzahlige Vielfache von $2 [mm] \pi [/mm] i$ eindeutig bestimmt.
> Bei wikipeida:
> http://de.wikipedia.org/wiki/Diskreter_Logarithmus
> Hier ist mir die Definition und die Schreibweise der exp
> und log Funktionen klar.
> Nun habe ich aber versucht in diesem Dokument auf der
> ersten Seite
>
> http://www.staff.uni-mainz.de/pommeren/Kryptologie/Asymmetrisch/4_DiskrLog/diskrlog.pdf
>
> dieses Diagramm nachzuvollziehen... warum definieren die da
> die exp-Funktion von [mm]\IZ \to[/mm] G und die log-Funktion dann
> von <a> [mm]\to \IZ_s?[/mm]
Warum nicht? Tut man bei der richtigen Exponentialfunktion doch auch, die ist auf ganz [mm] $\IC$ [/mm] definiert, und nicht auf [mm] $\IC [/mm] / 2 [mm] \pi [/mm] i [mm] \IZ$.
[/mm]
> Ist die Exponentialfunktion hier dann überhaupt die
> direkte Umkehrfunktion?
Nein. Die direkte Umkehrfunktion ist $h$, aber $h$ ist im Wesentlichen das gleiche wie [mm] $\exp_a$, [/mm] in dem Sinne dass $h(z + [mm] s\IZ) [/mm] = [mm] \exp_a(z)$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:14 So 31.07.2011 | | Autor: | Hanz |
Hallo,
danke schonmal für die sehr gute Antwort.
Habe ich das jetzt vllt. vorher nicht ganz richtig aufgefasst, weil im .pdf die [mm] exp_a [/mm] Funktion eine Exponentialfunktion ist und der Homomorphismus h wäre hier die DISKRETE Exponentialfunktion?
Kann man das so sagen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:38 So 31.07.2011 | | Autor: | felixf |
Moin!
> danke schonmal für die sehr gute Antwort.
>
> Habe ich das jetzt vllt. vorher nicht ganz richtig
> aufgefasst, weil im .pdf die [mm]exp_a[/mm] Funktion eine
> Exponentialfunktion ist und der Homomorphismus h wäre hier
> die DISKRETE Exponentialfunktion?
Das sind beides diskrete Exponentialfunktionen. Die eine laesst man halt bei [mm] $\IZ$ [/mm] losgehen, und die ist nicht injektiv, die andere bei [mm] $\IZ [/mm] / [mm] \ker \exp_a [/mm] = [mm] \IZ [/mm] / s [mm] \IZ$, [/mm] und sie ist damit injektiv.
Was man nun gerade mit diskrete Exponentialfunktion meint haengt einfach davon ab, ob man gerade moechte dass die Funktion injektiv ist, oder ob man das nicht braucht.
(Manchmal kennt man auch das $s$ nicht und kann deswegen nicht von [mm] $\IZ/s\IZ$ [/mm] ausgehen, obwohl man das eigentlich gern moechte.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:07 So 31.07.2011 | | Autor: | Hanz |
Achso, ok!
Ich hätte dann noch letzte Fragen und zwar was genau verstehe ich unter einer Periode eines Gruppenhomomorphismus?
Wenn ich die Graphik etwas abwandle wie im Anhang, habe ich doch keine grundlegenden Dinge hier verändert bzw. verfälscht, oder?
Ich möchte nämlich sagen, dass der diskrete Logarithmus eine Umkehrabbildung der diskreten Exponentialfunktion ist, also dass gilt
exp: [mm] \IZ_n \to [/mm] G
log: G [mm] \to \IZ_n
[/mm]
Anhand so eines Diagramms finde ich es eben auch anschaulich gut dargestellt, mich hat eben nur gestört, dass die exp-Funktion dort schon "anders benannt" wurde. Dann kann ich ja einfach sagen, ich habe eine Funktion f: [mm] \IZ \to [/mm] G und bennen mein induziertes h dann einfach diskrete Exponentialfunktion.
Geht das alles so, oder hzab ich etwas übersehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:14 So 31.07.2011 | | Autor: | felixf |
Moin!
> Ich hätte dann noch letzte Fragen und zwar was genau
> verstehe ich unter einer Periode eines
> Gruppenhomomorphismus?
Wenn der Gruppenhomomorphismus von einer Untergruppe von [mm] $\IR$ [/mm] weggeht, ist die Periode das kleinste positive Element im Kern - zumindest falls der Kern zyklisch ist.
> Wenn ich die Graphik etwas abwandle wie im Anhang, habe ich
> doch keine grundlegenden Dinge hier verändert bzw.
> verfälscht, oder?
Nein. Du benennst ja nur eine Funktion um.
> Ich möchte nämlich sagen, dass der diskrete Logarithmus
> eine Umkehrabbildung der diskreten Exponentialfunktion ist,
> also dass gilt
>
> exp: [mm]\IZ_n \to[/mm] G
> log: G [mm]\to \IZ_n[/mm]
Ja. Wobei du hier den Index $a$ nicht vergessen solltest, also [mm] $\exp_a$ [/mm] und [mm] $\log_a$. [/mm] Beide Funktionen haengen schliesslich von der Wahl des Elementes $a$ ab.
Und [mm] $\log_a$ [/mm] geht streng genommen bei [mm] $\langle [/mm] a [mm] \rangle$ [/mm] los, es sei denn $G = [mm] \langle [/mm] a [mm] \rangle$.
[/mm]
> Anhand so eines Diagramms finde ich es eben auch
> anschaulich gut dargestellt, mich hat eben nur gestört,
> dass die exp-Funktion dort schon "anders benannt" wurde.
> Dann kann ich ja einfach sagen, ich habe eine Funktion f:
> [mm]\IZ \to[/mm] G und bennen mein induziertes h dann einfach
> diskrete Exponentialfunktion.
>
> Geht das alles so, oder hzab ich etwas übersehen?
Ja, das kannst du so machen.
LG Felix
|
|
|
|
