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.

TheorieBearbeiten

Gesucht sei der diskrete Logarithmus   mit   eine endliche zyklische Gruppe der Ordnung   und   ein Gruppenelement.

Mittels Division mit Rest lässt sich zu einem fest gewählten   eine eindeutige Darstellung   mit   finden. Hierbei wird häufig   gewählt (siehe Landau-Symbole), um den möglichen Zahlenbereich der   und   ähnlich groß zu halten. Durch Umformen ergibt sich mit dieser Darstellung wegen   die dem Algorithmus zugrunde liegende Eigenschaft  .

Der Algorithmus sucht nach einem Paar  , das diese Eigenschaft erfüllt, und erstellt hierzu zunächst eine Tabelle der „baby steps“  . Anschließend berechnet man für wachsende   sukzessive die „giant steps“   und prüft auf Gleichheit mit einem Wert in der Tabelle. Liegt eine solche Kollision vor, ist dies das gesuchte Paar und der Logarithmus   wird ausgegeben.

Mit Zugriffszeiten auf einzelne Elemente der Tabelle von   – im Falle von geeignet schnellen Datenstrukturen wie Hashtabellen entspricht dies   – hat der Algorithmus eine Laufzeit von   mit Speicherbedarf  .

AlgorithmusBearbeiten

Eingabe: Endliche zyklische Gruppe  , Erzeuger  , Gruppenelement  

Ausgabe:   mit  

  • Berechne  ,   mit der Aufrundungsfunktion  .
  • Für alle  : Berechne   und speichere   in einer Tabelle.
  • Für alle  : Berechne   und suche danach in der zweiten Spalte der Tabelle. Wenn gefunden, gib   aus.

Wegen   lässt sich das Gruppenelement im letzten Schritt leicht aus dem der vorhergehenden Iteration berechnen.

BeispielBearbeiten

Weil   eine Primitivwurzel modulo   ist, gilt  . Sei also   die prime Restklassengruppe mit Erzeuger  . Wir wollen den diskreten Logarithmus von   zur Basis   berechnen, also die Lösung von  .

  • Die Gruppenordnung ergibt sich zu  , da   eine Primzahl ist (hierbei ist   die Eulersche φ-Funktion). Somit ist  .
  • Für   berechnet man die Paare   und speichert sie in einer Tabelle:
  0 1 2 3 4 5
  1 11 5 26 25 14
  • Es ist  . Man berechnet für   die Zahl   und terminiert, sobald sie in der zweiten Komponente der vorherigen Tabelle gefunden wurde:
  0 1 2
  3 10 14

Es ist also   und  , damit ist  .