Eindeutigkeit diskreter Logarithmus

30.12.2015, 10:31	lule	Auf diesen Beitrag antworten »
Eindeutigkeit diskreter Logarithmus Meine Frage: Guten Morgen, ich habe die Aufgabe: "Zeigen Sie, dass der diskrete Logarithmus in einer endlichen zyklischen Gruppe eindeutig ist" Ich wüsste gerne ob mein Beweis in Ordnung ist oder ob ich komplett falsch bin Meine Ideen: Sei $\begin{eqnarray} \left(G,\right) \end{eqnarray}$ eine endliche zyklische Gruppe und $\begin{eqnarray} b \in \mathbb G \end{eqnarray}$ , dann gilt $\begin{eqnarray} G = \left\{ a^k \| 0\leq k\leq n-1, k \in \mathbb Z \right\} \end{eqnarray}$ . Die Zahl $\begin{eqnarray} k \end{eqnarray}$ mit $\begin{eqnarray} b = a^k \end{eqnarray}$ lautet diskreter Lagarithmus von b zur Basis a $\begin{eqnarray} k = \log_{a}(b) \end{eqnarray}$ . Annahme: Sei k1, k2 diskreter Logaritmus von b zur Basis a NICHT eindeutig, also $\begin{eqnarray} k1 \neq k2 \end{eqnarray}$ $\begin{eqnarray} k1 = \log_{a}(b)<=> b = a^{k1} \end{eqnarray}$ $\begin{eqnarray} k2 = \log_{a}(b)<=> b = a^{k2} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow a^{k1} = a^{k2} \end{eqnarray}$ $\begin{eqnarray} <=> k1 = k2 \end{eqnarray*}$ Dies ist aber ein Widerspruch, daher muss k eindeutig sein. Wäre das in Ordung so ? MfG
30.12.2015, 12:58	Elvis	Auf diesen Beitrag antworten »
Wieso gilt diese Implikation $\begin{eqnarray} a^{k_1}=a^{k_2}\Rightarrow k_1=k_2 \end{eqnarray}$ ? Sie gilt jedenfalls nicht für das neutrale Element $\begin{eqnarray} e^7=e^3=e \end{eqnarray}$ , aber $\begin{eqnarray} 7\ne 3 \end{eqnarray}$ . Du musst deine Aussagen und Beweise mit allen Quantoren exakt formulieren und durchführen.
31.12.2015, 16:41	lule	Auf diesen Beitrag antworten »
Hey Elvis, ja stimmt für das neutrale Element gilt dies nicht. Wie genau meinst du das "Aussagen und Beweise mit allen Quantoren exakt formulieren und durchführen" ? Aber ich hab eine Idee wie man es vielleicht Zeigen kann, dass die Implikation gilt. (Außer für das neutrale Element) Es gelte $\begin{eqnarray} a^{k1} = a^{k2}, \end{eqnarray}$ mit $\begin{eqnarray} k1 ,k2 \leq n-1 \end{eqnarray}$ und $\begin{eqnarray} k1 \neq k2 \end{eqnarray}$ dann muss doch aber $\begin{eqnarray} k2 = k1 +t , t \leq n-1 \end{eqnarray}$ gelten. Also: $\begin{eqnarray} a^{k1} = a^{k1} a^{t} \end{eqnarray}$ $\begin{eqnarray} a^{-k1} a^{k1} = a^{-k1} a^{k1} * a^{t} \end{eqnarray}$ $\begin{eqnarray} e = e * a^{t} \end{eqnarray}$ $\begin{eqnarray} e = a^{t} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow k1 = k2 \end{eqnarray*}$ So in etwa ? Oder bin ich gerade voll auf dem Holzweg ?
31.12.2015, 19:06	Elvis	Auf diesen Beitrag antworten »
Sehr holziger Weg. Wenn man den diskreten Logarithmus als Umkehrfunktion der diskreten Exponentiation definiert und beweist, dass diese ein Gruppenisomorphismus ist, ist die Eindeutigkeit des diskreten Logarithmus klar. (https://de.wikipedia.org/wiki/Diskreter_Logarithmus) . Wenn Du eine andere Definition des Logarithmus hast, musst Du diese angeben und damit argumentieren. Wie definierst Du den diskreten Logarithmus für die zyklische Gruppe G=({0,1,2},+) mit (01,11,21)=(02,22,12) ? Es gibt hier 2 Erzeuger der Gruppe, und der diskrete Logarithmus ist von dem Erzeuger abhängig. Was heißt dann Eindeutigkeit ?
04.01.2016, 17:34	lule	Auf diesen Beitrag antworten »
Ach mist Ja gut damit geht es dann, aber wie kommt man denn auf sowas ? Da soll nochmal jemand sagen, Mathe hat nichts mit Kreativität zu tun. Ich würde sagen das sich die Eindeutigkeit hier auf die Basis bezieht, bzw. der diskrete Logarithmus ist nur eindeutig bei gleicher Basis. Wir haben den diskreten Logarithmus so definiert: Sei (G,) eine endliche, zyklische Gruppe und a ein erzeugendes Element. Sei $\begin{eqnarray} b\in G \end{eqnarray}$ . Die eindeutig bestimmte Zahl $\begin{eqnarray} k, 0\leq k\leq n-1 \end{eqnarray}$ , n = #G mit $\begin{eqnarray} b = a^k \end{eqnarray}$ heißt diskreter Logarithmus von b zur Basis a $\begin{eqnarray} k = \log_a b \end{eqnarray*}$
04.01.2016, 18:36	Elvis	Auf diesen Beitrag antworten »
Def: Die eindeutig bestimmte Zahl k heißt eindeutig bestimmter diskreter Logarithmus. Demnach kann der Logarithmus per definitionem nur eindeutig sein. Klingt wie der ontologische Gottesbeweis von Anselm von Canterbury. Def: Gott ist das, worüber hinaus Größeres nicht gedacht werden kann. Existenzbeweis: Wer die Existenz des so def. Gottes nicht glaubt, unterliegt einem Selbstwiderspruch. (Wäre Gott nur ein Gedanke, dann könnte ein wirklich existierender Gott gedacht werden, dieser wäre größer als der nur gedachte Gott.) Auf die Definition des Logarithmus als Umkehrfunktion der Exponentialfunktion kommt man dadurch, dass dies die universale Definition ist : $\begin{eqnarray} log:=exp^{-1} \end{eqnarray}$ .
Anzeige

06.01.2016, 16:14	lule	Auf diesen Beitrag antworten »
Hey Also ich wage mal zu behaupten, dass das nicht die Lösung ist die sich mein Prof dabei gedacht hat Aber ich werde ihn da mal fragen Mit gefällt der Ansatz mit der Umkehrfunktion übrigends auch besser, danke dafür nochmal Und den Gottesbeweis kannte ich auch noch nicht Danke auch dafür !

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »