WikiDer > Diskreter Logarithmus

Innerhalb der Mathematik ist der diskreter Logarithmus das Äquivalent innerhalb von a endliche Menge, des regelmäßiger Logarithmus über die Sammlung der reale Nummern. Der diskrete Logarithmus ist in jedem . definiert zyklische Gruppe.

Erläuterung

spät ${Anzeigestil G}$ ein zyklische Gruppe sei, endlich oder unendlich, ${displaystyle Gin G}$ ein Urheber von ${Anzeigestil G}$, und ${Anzeigestil hin G}$. Dann ist ${Anzeigestil h=g^{m}}$ sicher ${displaystyle m}$. Analog zum gewöhnlichen Logarithmus ist die Potenz ${displaystyle m}$ der diskrete Logarithmus von ${displaystyle h}$ an der Wurzel ${displaystyle g}$. In Formel

${displaystyle m={}^{g}!log h}$,

oder

${displaystyle m=log _{g}h}$.

Die Nummer ${displaystyle m}$ ist in diesem Fall eindeutig bestimmt.

Wenn die Gruppe endlicher Ordnung ist ${displaystyle n}$, kann auch ein diskreter Logarithmus definiert werden, aber dann modulo ${displaystyle n}$ ist eindeutig.

In der Praxis wird der diskrete Logarithmus angewendet auf endlich zyklische Gruppen. Wählt man a Primzahl für die Ordnung der Gruppe, dann ist der diskrete Logarithmus schwieriger mit Pohlig-Hellman-Algorithmus berechnen.

Beispiel

Die Sammlung ${Displaystil G={1,2,ldots 6}}$ Bildet bei der Berechnung von Modulo 7 eine zyklische Gruppe der Ordnung 6 für die Multiplikation als Gruppenbearbeitung. Die Zahl 5 ist ein Generator von ${Anzeigestil G}$, sodass alle Elemente geschrieben werden können als ${displaystyle 5^{i},iin mathbb {N} }$.

${displaystyle { egin{matrix}5^{1}&=&5&&&equiv &5&{pmod {7}}/5^{2}&=&25&=&3cdot 7 4&equiv &4&{pmod {7}}/5^{3}&= &125&=&17cdot 7 6&equiv &6&{pmod {7}}/5^{4}&=&625&=&89cdot 7 2&equiv &2&{pmod {7}}/5^{5}&=&3125&=&446cdot 7 3&equiv &3&{pmod {7 }}/5^{6}&=&15625&=&2232cdot 7 1&Äquiv. &1&{pmod {7}}end{matrix}}}$

Nimm jetzt ${Anzeigestil g=5}$ und ${Anzeigestil h=4}$. Gesucht ist die Nummer ${displaystyle n={}^{5}!log 4}$ auf was trifft das zu ${displaystyle 4Äquiv. 5^{n}{pmod {7}}}$. Die obige Zusammenfassung zeigt, dass ${Anzeigestil n=2}$. Diese Methode, die eigentlich alle Möglichkeiten prüft, nutzt rohe Gewalt und kann nur in einfachen Fällen richtig angewendet werden.

Eine bequemere Methode ist, eine Zahl zu finden ${Anzeigestil s}$ was auch geschrieben werden kann als ${displaystyle s=kcdot 7 4,kin mathbb {N}}$ und als Potenz von 5. Dann gilt: ${displaystyle s=5^{n}äquivalent 4{pmod {7}}}$. Die Nummer ${Anzeigestil s=25}$ reicht, also ${Anzeigestil n=2}$.

Es Diffie-HellmanProtokoll und die Elgamal-Verschlüsselungssystem Machtprodukte bedienen, wobei die einzelnen Exponenten als Geheimcode verborgen bleiben können.

Bei der Wahl einer großen Ordnung der Gruppe ist es schwierig, das Problem durch Tabellenerstellung zu lösen, da es dafür viel zu viele Möglichkeiten gibt. Die folgenden Methoden bieten Möglichkeiten, die z.B. ${displaystyle mathbb {Z} }$${displaystyle _{p}}$${Anzeigestil ^{*}}$, ${displaystyle mathbb {F} }$${displaystyle _{q}}$${Anzeigestil ^{*}}$ und ${displaystyle mathbb {F} _{2^{m}}}$${Anzeigestil ^{*}}$

Siehe auch

• Baby Schritte Riesenschritte Algorithmus
• Indexberechnungsalgorithmus
• Pohlig-Hellman-Algorithmus
• Lambda-Algorithmus von Pollardard
• Der Rho-Algorithmus von Pollard

Verweise

• (und) Alfred J. Menezes, Paul C. van Oorschot & Scott A. Vanstone, Handbuch der angewandten Kryptographie, 2001.
• (und) DJ Bernstein, Generische Angriffe und Indexkalküle, Universität von Illinois, Chicago.
• (und) Neal Koblitz, Ein Kurs in elementarer Zahlentheorie und Kryptographie, Springer.