imported>Oluna2078: Removed a duplicate line.

2025-03-21T16:09:07Z

Removed a duplicate line.

Neue Seite

In der [[Gruppentheorie]] und [[Zahlentheorie]] ist der '''diskrete Logarithmus''' das Analogon zum gewöhnlichen [[Logarithmus]] aus der [[Analysis]]; ''diskret'' kann in diesem Zusammenhang etwa wie ''ganzzahlig'' verstanden werden. Die [[Diskrete Exponentialfunktion|diskrete Exponentiation]] in einer [[Zyklische Gruppe|zyklischen Gruppe]] ist die [[Umkehrfunktion]] des diskreten Logarithmus. Als Vergleich: Die natürliche [[Exponentialfunktion]] auf den [[Reelle Zahl|reellen Zahlen]] ist die Umkehrfunktion des [[Natürlicher Logarithmus|natürlichen Logarithmus]].

Ein wichtiger Anwendungsfall tritt beim [[Kongruenz (Zahlentheorie)|Rechnen modulo ''p'']] auf. Der diskrete Logarithmus von <math>m</math> zur Basis <math>a</math> ist hier der kleinste Exponent <math>x</math> der Gleichung <math display="inline">a^x \equiv m \mod p</math> bei gegebenen natürlichen Zahlen <math>m</math>, <math>a</math> und der [[Primzahl]] <math>p</math>. Zum Beispiel ist beim Rechnen modulo <math display="inline">11</math> der diskrete Logarithmus von <math>5</math> zur Basis <math>2</math> gleich <math display="inline">4</math>, da <math display="inline">2^4 = 16 \equiv 5 \mod 11</math> ist.

Da für den diskreten Logarithmus meist nur ineffiziente (im Sinne der [[Komplexitätstheorie]]) Algorithmen bekannt sind, während sich die Umkehrfunktion, die diskrete Exponentialfunktion, leicht (im Sinne der Komplexitätstheorie) berechnen lässt, eignet sich die diskrete Exponentialfunktion als [[Einwegfunktion]] in der [[Kryptografie]]. Anwendungsbeispiele sind u. a.
* [[Diffie-Hellman-Schlüsselaustausch]]
* [[Elgamal-Signaturverfahren]]
* [[Schnorr-Signatur|Schnorr-Signaturverfahren]]
* [[Digital Signature Algorithm|DSA-Verfahren]]
* [[Elliptic Curve Cryptography|Elliptische-Kurven-Kryptosystem]]

== Theorie ==
=== Allgemeine Definition ===
Es sei <math display="inline">(G,\circ)</math> eine endliche [[zyklische Gruppe]] mit Erzeuger <math display="inline">g</math> der [[Ordnung eines Gruppenelementes|Ordnung]] <math display="inline">n</math>. Mit der [[Restklassengruppe]] <math display="inline">\Z/n\Z</math> ist die diskrete Exponentiation
:<math display="inline">\begin{align}
\exp_g\colon \Z/n\Z &\to G \\
x &\mapsto g^x
\end{align}</math>
ein [[Gruppenisomorphismus]]. Die zugehörige Umkehrfunktion
:<math display="inline">\begin{align}
\log_g\colon G &\to \Z/n\Z\\
x & \mapsto \log_g x
\end{align}</math>
heißt ''diskreter Logarithmus'' zur Basis <math display="inline">g</math>.

Die bekannte Basiswechselformel bleibt gültig: Ist <math>h</math> ein weiterer Erzeuger, dann ist
:<math display="inline">\log_h x = \log_h g \cdot \log_g x \mod n</math>.

Weiterhin gilt die folgende Beziehung für den diskreten Logarithmus, die der Funktionalgleichung des Logarithmus entspricht:
:<math display="inline">\log_g x + \log_g y = \log_g (x\circ y) \mod n</math>.

=== Prime Restklassengruppe ===
Von praktischem Nutzen in der Kryptografie ist der Spezialfall, wenn die zyklische Gruppe eine [[prime Restklassengruppe]] ist, insbesondere modulo Primzahlen.

Sei <math display="inline">p</math> eine [[Primzahl]] und <math>g</math> eine [[Primitivwurzel]] modulo <math display="inline">p</math>, also ein Erzeuger der primen Restklassengruppe <math display="inline">(\Z /p \Z)^\times</math>. Der diskrete Logarithmus (auch ''Index'' genannt) einer zu <math display="inline">p</math> teilerfremden Zahl <math>x</math> zur Basis <math>g</math> ist definiert als die eindeutig bestimmte Zahl <math display="inline">a \in \{1,2,\dotsc,p-1\}</math> mit:
:<math display="inline">g^a \equiv x \mod{p}</math>
und wird mit <math display="inline">a = \log_g x</math> bzw. <math display="inline">a = \operatorname{ind}_g x</math> bezeichnet (zur Schreibweise siehe [[Kongruenz (Zahlentheorie)]] und [[modulo]]).

== Algorithmen zur Berechnung des diskreten Logarithmus ==
Es sind bisher keine [[Effizienz (Informatik)|schnellen]] Algorithmen zur Berechnung des diskreten Logarithmus bekannt. Deren Laufzeit verhielte sich polynomial zur Länge der Eingabe. Es gibt aber Algorithmen, die die Lösung gezielter finden als bloßes [[Brute Force|Ausprobieren]]. Aufgrund des angesprochenen Laufzeitverhaltens und der in der Kryptografie üblichen Größenordnungen (mehrere hundert Dezimalstellen in Numerus und Basis) spielen sie praktisch aber keine Rolle. Zu den bekanntesten Algorithmen zählen:
* [[Babystep-Giantstep-Algorithmus]]
* [[Pohlig-Hellman-Algorithmus]]
* [[Index-Calculus-Algorithmus]]
* [[Pollard-Rho-Methode]]
* [[Zahlkörpersieb]]

== Beispiel ==
Als Beispiel diene die [[Primzahl]] <math display="inline">p = 11</math> und die zugehörige prime Restklassengruppe <math display="inline">G = (\Z /11 \Z)^\times=\{1,2,\dotsc,10\}</math>. Zur Primitivwurzel <math display="inline">g = 2</math> wird nun die Wertetabelle der diskreten Exponentiation bestimmt.

: <math display="inline">\begin{array}{lcrlrl}
2^1 &=& 2 &\equiv & 2 &\mod{11}\\
2^2 &=& 4 &\equiv & 4 &\mod{11}\\
2^3 &=& 8 &\equiv & 8 &\mod{11}\\
2^4 &=& 16 &\equiv & 5 &\mod{11}\\
2^5 &=& 32 &\equiv & 10 &\mod{11}\\
2^6 &=& 64 &\equiv & 9 &\mod{11}\\
2^7 &=& 128 &\equiv & 7 &\mod{11}\\
2^8 &=& 256 &\equiv & 3 &\mod{11}\\
2^9 &=& 512 &\equiv & 6 &\mod{11}\\
2^{10} &=& 1024 &\equiv & 1 &\mod{11}
\end{array}</math>

{| class="wikitable" style="text-align:right"
|-
| <math display="inline">a</math> || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">2^a \mod 11</math> || 2 || 4 || 8 || 5 || 10 || 9 || 7 || 3 || 6 || 1
|}

Dass es sich bei <math>g</math> tatsächlich um eine Primitivwurzel modulo 11 handelt, ist an den paarweise verschiedenen diskreten Potenzen erkennbar. Mit anderen Worten, die gesamte prime Restklassengruppe kann mithilfe der diskreten Potenzen von <math>g</math> erzeugt werden. Durch Vertauschen der Zeilen und Sortieren erhält man die Wertetabelle des diskreten Logarithmus.

{| class="wikitable" style="text-align:right"
|-
| <math display="inline">x</math> || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">\log_2 x</math> || 10 || 1 || 8 || 2 || 4 || 9 || 7 || 3 || 6 || 5
|}

== Literatur ==
* Erich Härtter: ''Wahrscheinlichkeitsrechnung, Statistik und mathematische Grundlagen. Begriffe, Definitionen und Formeln''. Verlag Vandenhoeck & Ruprecht, Göttingen 1987, ISBN 3-525-40731-9.

[[Kategorie:Zahlentheorie]]

Diskreter Logarithmus - Versionsgeschichte

imported>Oluna2078: Removed a duplicate line.