Babystep-Giantstep-Algorithmus

Der Babystep-Giantstep-Algorithmus (auch Shanks’ Algorithmus für diskrete Logarithmen genannt) berechnet den diskreten Logarithmus eines Elements einer zyklischen Gruppe. Der Algorithmus ist zwar in der Laufzeit dem naiven Ausprobieren aller Möglichkeiten überlegen, ist aber dennoch für sehr große Gruppen praktisch nicht durchführbar. Der Algorithmus stammt von 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:

• 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:

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