Babystep-Giantstep-Algorithmus

Der Babystep-Giantstep-Algorithmus (auch Shanks’ Algorithmus für diskrete Logarithmen genannt) berechnet d​en diskreten Logarithmus e​ines Elements e​iner zyklischen Gruppe. Der Algorithmus i​st zwar i​n der Laufzeit d​em naiven Ausprobieren a​ller Möglichkeiten überlegen, i​st aber dennoch für s​ehr große Gruppen praktisch n​icht durchführbar. Der Algorithmus stammt v​on Daniel Shanks.

Theorie

Gesucht sei der diskrete Logarithmus ${\displaystyle x:=\log _{g}a}$ mit ${\displaystyle \langle g\rangle =\{g^{0},g^{1},\dotsc g^{n-1}\}}$ eine endliche zyklische Gruppe der Ordnung ${\displaystyle n}$ und ${\displaystyle a=g^{x}}$ ein Gruppenelement.

Mittels Division mit Rest lässt sich zu einem fest gewählten ${\displaystyle m}$ eine eindeutige Darstellung ${\displaystyle x=im+j}$ mit ${\displaystyle 0\leq j<m}$ finden. Hierbei wird häufig ${\displaystyle m\in \Theta ({\sqrt {n}})}$ gewählt (siehe Landau-Symbole), um den möglichen Zahlenbereich der ${\displaystyle i}$ und ${\displaystyle j}$ ähnlich groß zu halten. Durch Umformen ergibt sich mit dieser Darstellung wegen ${\displaystyle a=g^{x}=g^{im+j}}$ die dem Algorithmus zugrunde liegende Eigenschaft ${\displaystyle g^{j}=ag^{-im}}$.

Der Algorithmus sucht nach einem Paar ${\displaystyle (i,j)}$, das diese Eigenschaft erfüllt, und erstellt hierzu zunächst eine Tabelle der „baby steps“ ${\displaystyle (j,g^{j})}$. Anschließend berechnet man für wachsende ${\displaystyle i}$ sukzessive die „giant steps“ ${\displaystyle a(g^{-m})^{i}}$ und prüft auf Gleichheit mit einem Wert in der Tabelle. Liegt eine solche Kollision vor, ist dies das gesuchte Paar und der Logarithmus ${\displaystyle im+j}$ wird ausgegeben.

Mit Zugriffszeiten auf einzelne Elemente der Tabelle von ${\displaystyle {\mathcal {O}}(\alpha )}$ – im Falle von geeignet schnellen Datenstrukturen wie Hashtabellen entspricht dies ${\displaystyle {\mathcal {O}}(1)}$ – hat der Algorithmus eine Laufzeit von ${\displaystyle {\mathcal {O}}((n/m)\cdot \alpha ^{2})}$ mit Speicherbedarf ${\displaystyle {\mathcal {O}}(m)}$.

Algorithmus

Eingabe: Endliche zyklische Gruppe ${\displaystyle G}$, Erzeuger ${\displaystyle g}$, Gruppenelement ${\displaystyle a}$

Ausgabe: ${\displaystyle x:=\log _{g}a}$ mit ${\displaystyle g^{x}=a}$

• Berechne ${\displaystyle n:=|G|}$, ${\displaystyle m:=\lceil {\sqrt {n}}\rceil }$ mit der Aufrundungsfunktion ${\displaystyle \lceil \cdot \rceil }$.
• Für alle ${\displaystyle j\in \{0,\dots ,m-1\}}$: Berechne ${\displaystyle g^{j}}$ und speichere ${\displaystyle (j,g^{j})}$ in einer Tabelle.
• Für alle ${\displaystyle i\in \{0,\dots ,m-1\}}$: Berechne ${\displaystyle a(g^{-m})^{i}}$ und suche danach in der zweiten Spalte der Tabelle. Wenn gefunden, gib ${\displaystyle im+j}$ aus.

Wegen ${\displaystyle a(g^{-m})^{i}=a(g^{-m})^{i-1}g^{-m}}$ lässt sich das Gruppenelement im letzten Schritt leicht aus dem der vorhergehenden Iteration berechnen.

Beispiel

Weil ${\displaystyle 11}$ eine Primitivwurzel modulo ${\displaystyle 29}$ ist, gilt ${\displaystyle (\mathbb {Z} /29\mathbb {Z} )^{\times }=\langle 11\rangle }$. Sei also ${\displaystyle G:=(\mathbb {Z} /29\mathbb {Z} )^{\times }}$ die prime Restklassengruppe mit Erzeuger ${\displaystyle g:=11}$. Wir wollen den diskreten Logarithmus von ${\displaystyle a:=3}$ zur Basis ${\displaystyle g}$ berechnen, also die Lösung von ${\displaystyle 3=11^{x}\mod 29}$.

• Die Gruppenordnung ergibt sich zu ${\displaystyle n:=\varphi (29)=28}$, da ${\displaystyle 29}$ eine Primzahl ist (hierbei ist ${\displaystyle \varphi }$ die Eulersche φ-Funktion). Somit ist ${\displaystyle m:=\lceil {\sqrt {28}}\rceil =6}$.
• Für ${\displaystyle j\in \{0,\dots ,5\}}$ berechnet man die Paare ${\displaystyle (j,11^{j})}$ und speichert sie in einer Tabelle:

${\displaystyle j}$	0	1	2	3	4	5
${\displaystyle 11^{j}}$	1	11	5	26	25	14

• Es ist ${\displaystyle 11^{-6}=11^{28-6}=13}$. Man berechnet für ${\displaystyle i\in \{0,\dots ,5\}}$ die Zahl ${\displaystyle 3\cdot 13^{i}}$ und terminiert, sobald sie in der zweiten Komponente der vorherigen Tabelle gefunden wurde:

${\displaystyle i}$	0	1	2
${\displaystyle 3\cdot 13^{i}}$	3	10	14

Es ist also ${\displaystyle i=2}$ und ${\displaystyle j=5}$, damit ist ${\displaystyle \log _{11}3=2\cdot 6+5=17}$.