Diskreter Logarithmus

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 Exponentiation in einer zyklischen Gruppe ist die Umkehrfunktion des diskreten Logarithmus. Als Vergleich: Die natürliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des natürlichen Logarithmus.

Ein wichtiger Anwendungsfall tritt beim Rechnen modulo p auf. Der diskrete Logarithmus von ${\displaystyle m}$ zur Basis ${\displaystyle a}$ ist hier der kleinste Exponent ${\displaystyle x}$ der Gleichung ${\textstyle a^{x}\equiv m\mod p}$ bei gegebenen natürlichen Zahlen ${\displaystyle m}$, ${\displaystyle a}$ und der Primzahl ${\displaystyle p}$. Zum Beispiel ist beim Rechnen modulo ${\textstyle 11}$ der diskrete Logarithmus von ${\displaystyle 5}$ zur Basis ${\displaystyle 2}$ gleich ${\textstyle 4}$, da ${\textstyle 2^{4}=16\equiv 5\mod 11}$ 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-Signaturverfahren
• DSA-Verfahren
• Elliptische-Kurven-Kryptosystem