imported>Aka: Tippfehler entfernt, Kleinkram

2025-03-15T22:31:00Z

Neue Seite

Der '''Babystep-Giantstep-Algorithmus''' (auch '''Shanks’ Algorithmus''' für diskrete Logarithmen genannt) berechnet den [[Diskreter Logarithmus|diskreten Logarithmus]] eines Elements einer [[Zyklische Gruppe|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]].<ref name=":0">{{Literatur |Autor=Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger |Titel=Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen |Verlag=Walter de Gruyter |Datum=2013-05-28 |ISBN=978-3-11-031261-4 |Seiten=100 |Online=https://www.google.de/books/edition/Diskrete_algebraische_Methoden/XGNKsOm9r3IC?hl=de&gbpv=1&dq=Babystep-Giantstep-Algorithmus&pg=PA100&printsec=frontcover |Abruf=2025-03-15}}</ref>

== Theorie ==
Gesucht sei der diskrete Logarithmus <math>x := \log_g a</math> mit <math>\langle g \rangle = \{g^0, g^1, \dotsc g^{n-1}\}</math> eine endliche zyklische Gruppe der Ordnung <math>n</math> und <math>a = g^x</math> ein Gruppenelement.

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

Der Algorithmus sucht nach einem Paar <math>(i,j)</math>, das diese Eigenschaft erfüllt, und erstellt hierzu zunächst eine Tabelle der „baby steps“ <math>(j, g^j)</math>. Anschließend berechnet man für wachsende <math>i</math> sukzessive die „giant steps“ <math>a(g^{-m})^i</math> und prüft auf Gleichheit mit einem Wert in der Tabelle. Liegt eine solche Kollision vor, ist dies das gesuchte Paar und der Logarithmus <math>im+j</math> wird ausgegeben.<ref>{{Literatur |Autor=Johannes Buchmann |Titel=Einführung in die Kryptographie |Verlag=Springer-Verlag |Datum=2013-03-08 |ISBN=978-3-642-98060-2 |Seiten=150ff |Online=https://www.google.de/books/edition/Einf%C3%BChrung_in_die_Kryptographie/mbepBgAAQBAJ?hl=de&gbpv=1&dq=Babystep-Giantstep-Algorithmus&pg=PA150&printsec=frontcover |Abruf=2025-03-15}}</ref>

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

== Algorithmus ==
'''Eingabe:''' Endliche zyklische Gruppe <math>G</math>, Erzeuger <math>g</math>, Gruppenelement <math>a</math>

'''Ausgabe:''' <math>x:=\log_g a</math> mit <math>g^x=a</math>

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

Wegen <math>a(g^{-m})^i = a(g^{-m})^{i-1}g^{-m}</math> lässt sich das Gruppenelement im letzten Schritt leicht aus dem der vorhergehenden Iteration berechnen.<ref>{{Literatur |Autor=Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter |Titel=Moderne Verfahren der Kryptographie: Von RSA zu Zero-Knowledge |Verlag=Springer-Verlag |Datum=2013-03-08 |ISBN=978-3-322-84306-7 |Seiten=124 |Online=https://www.google.de/books/edition/Moderne_Verfahren_der_Kryptographie/iSudBgAAQBAJ?hl=de&gbpv=1&dq=Babystep-Giantstep-Algorithmus&pg=PA138&printsec=frontcover |Abruf=2025-03-15}}</ref>

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

* Die Gruppenordnung ergibt sich zu <math>n:=\varphi(29)=28</math>, da <math>29</math> eine Primzahl ist (hierbei ist <math>\varphi</math> die [[Eulersche φ-Funktion]]). Somit ist <math>m:=\lceil\sqrt{28}\rceil=6</math>.
* Für <math>j\in\{0,\dots,5\}</math> berechnet man die Paare <math>(j, 11^j)</math> und speichert sie in einer Tabelle:
{| style="margin-left:3em" border="1" cellspacing="0" cellpadding="3"
| <math>j</math> || 0 || 1 || 2 || 3 || 4 || 5
|-
| <math>11^j</math> || 1 || 11 || 5 || 26 || 25 || 14
|}
* Es ist <math>11^{-6} = 11^{28-6} = 13</math>. Man berechnet für <math>i\in\{0,\dots,5\}</math> die Zahl <math>3 \cdot 13^i</math> und terminiert, sobald sie in der zweiten Komponente der vorherigen Tabelle gefunden wurde:
{| style="margin-left:3em" border="1" cellspacing="0" cellpadding="3"
| <math>i</math> || 0 || 1 || 2
|-
| <math>3 \cdot 13^i</math> || 3 || 10 || 14
|}

Es ist also <math>i=2</math> und <math>j=5</math>, damit ist <math>\log_{11} 3 = 2\cdot 6 + 5 = 17</math>.

== Einzelnachweise ==
<references />
[[Kategorie:Zahlentheoretischer Algorithmus]]

Babystep-Giantstep-Algorithmus - Versionsgeschichte

imported>Aka: Tippfehler entfernt, Kleinkram