Babystep-Giantstep-Algorithmus

Der Babystep-Giantstep-Algorithmus 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 x: = log ga mit \langle g \rangle endliche zyklische Gruppe der Ordnung n und a Gruppenelement.

Mittels Division durch Rest lässt sich zu einem fest gewählten m eine eindeutige Darstellung x = im + j, 0 \le j < m finden. Hierbei wird häufig m := \Theta(\sqrt{n}) gewählt, um den möglichen Zahlenbereich der i und j ähnlich groß zu halten. Durch Umformen ergibt sich mit dieser Darstellung wegen a = gx = gim + j die dem Algorithmus zugrundeliegende Eigenschaft gj = ag im.

Der Algorithmus sucht nach einem Paar (i,j), das diese Eigenschaft erfüllt, und erstellt hierzu zunächst eine Tabelle der „baby steps“ (j,gj). Anschließend berechnet man für wachsende i sukzessive die „giant steps“ {ag^{(-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 im + j wird ausgegeben.

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

Algorithmus

Eingabe: Endliche zyklische Gruppe G, Erzeuger g, Gruppenelement a

Ausgabe: x: = logga mit gx = a

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

Wegen a(g m)i = a(g m)i − 1g m lässt sich das Gruppenelement im letzten Schritt leicht aus dem der vorhergehenden Iteration berechnen.

Beispiel

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

  • Die Gruppenordnung ergibt sich zu n: = φ(29) = 28, da 29 eine Primzahl ist (hierbei ist φ die Eulersche φ-Funktion). Somit ist m:=\lceil\sqrt{28}\rceil=6.
  • Für j\in\{0,\dots,5\} berechnet man die Paare (j,11j) und speichert sie in einer Tabelle:
j 0 1 2 3 4 5
11j 1 11 5 26 25 14
  • Es ist 11 − 6 = 1128 − 6 = 13. Man berechnet für i\in\{0,\dots,5\} die Zahl 3 \cdot 13^i und terminiert, sobald sie in der zweiten Komponente der vorherigen Tabelle gefunden wurde:
i 0 1 2
3 \cdot 13^i 3 10 14
Es ist also i = 2 und j = 5, damit ist \log_{11} 3 = 2\cdot 6 + 5 = 17.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Silver-Pohlig-Hellman-Algorithmus — Der Pohlig Hellman Algorithmus wurde nach den Mathematikern Stephen Pohlig und Martin Hellman benannt. Gelegentlich ist dieser Algorithmus in der Literatur auch unter dem Namen Silver Pohlig Hellman Algorithmus zu finden. Mit dem Pohlig Hellman… …   Deutsch Wikipedia

  • Pohlig-Hellman-Algorithmus — Der Pohlig Hellman Algorithmus wurde nach den Mathematikern Stephen Pohlig und Martin Hellman benannt. Gelegentlich ist dieser Algorithmus in der Literatur auch unter dem Namen Silver Pohlig Hellman Algorithmus zu finden. Mit dem Pohlig Hellman… …   Deutsch Wikipedia

  • Diskreter-Logarithmus-Problem — In der Gruppentheorie 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… …   Deutsch Wikipedia

  • Bsgs — Der Babystep Giantstep Algorithmus 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 …   Deutsch Wikipedia

  • Diskreter Logarithmus — In der Gruppentheorie 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… …   Deutsch Wikipedia

  • Elliptic Curve Cryptography — Elliptische Kurve über Unter Elliptic Curve Cryptography (ECC) oder deutsch Elliptische Kurven Kryptographie versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern v …   Deutsch Wikipedia

  • Time-Memory Tradeoff — In der Informatik ist ein Time Memory Tradeoff (TMTO, deutsch Zeit Speicher Kompromiss oder Zeit Speicher Ausgleich) ein Kompromiss, bei dem der Speicherbedarf eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”