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 <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.

Theorie

Allgemeine Definition

Es sei <math display="inline">(G,\circ)</math> eine endliche zyklische Gruppe mit Erzeuger <math display="inline">g</math> der 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 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 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:

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>

<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.

<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.