Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Babystep-Giantstep-Algorithmus aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

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.

Theorie

Sei $G=\backslash langle\; g\backslash rangle$ eine endliche zyklische Gruppe der Ordnung $n$, sei $m:=\backslash lceil\backslash sqrt\{n\}\backslash rceil$. Sei $a$ ein Gruppenelement, sei $x:=\backslash log\_g\; a$ der diskrete Logarithmus von $a$ zur Basis $g$, d.h. die modulo $n$ eindeutig bestimmte Zahl mit $a=g^x$. Mit Division mit Rest gibt es dann eindeutige
:$g^j\; =\; ag^\{-im\}$.
Der Algorithmus berechnet $g^j$ für alle $j$ und danach $ag^\{-im\}$ für wachsendes $i$, bis der Wert einem $g^j$ entspricht. Dann gibt er $x=im+j$ aus.

Algorithmus

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

Ausgabe: $x:=\backslash log\_g\; a$ mit $g^x=a$

* Berechne $n:=|G|$, $m:=\backslash lceil\backslash sqrt\{n\}\backslash rceil$
* Für alle $j\backslash in\backslash \{0,\backslash dots,m-1\backslash \}$: Berechne $g^j$ und speichere $(j,g^j)$ in einer Tabelle.
* Für alle $i\backslash in\backslash \{0,\backslash dots,m-1\backslash \}$: 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-1\}g^\{-m\}$ lässt sich das Gruppenelement im letzten Schritt leicht aus dem der vorhergehenden Iteration berechnen.

In der Praxis

Für die Datenhaltung von $(j,g^j)$ empfiehlt es sich, eine Hashtabelle zu verwenden, wobei der Hash-Wert von $g^j$ berechnet wird. Weil der Zugriff auf eine Hashtabelle in $O(1)$ liegt, verlangsamt dies den Algorithmus nicht.

Sowohl Zeit- als auch Platzkomplexität liegen in $O(\backslash sqrt\{n\})$.

Beispiel

Weil $11$ eine Primitivwurzel modulo $29$ ist, gilt $(\backslash mathbb\{Z\}/29\backslash mathbb\{Z\})^\backslash times\; =\; \backslash langle\; 11\; \backslash rangle$. Sei also $G:=(\backslash mathbb\{Z\}/29\backslash mathbb\{Z\})^\backslash 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:=\backslash varphi(29)=28$, da $29$ eine Primzahl ist (hierbei ist $\backslash varphi$ die Eulersche ?-Funktion). Somit ist $m:=\backslash lceil\backslash sqrt\{28\}\backslash rceil=6$.
* Für $j\backslash in\backslash \{0,\backslash dots,5\backslash \}$ berechnet man die Paare $(j,\; 11^j)$ und speichert sie in einer Tabelle:
:
* Es ist $11^\{-6\}\; =\; 11^\{28-6\}\; =\; 13$. Man berechnet für $i\backslash in\backslash \{0,\backslash dots,5\backslash \}$ die Zahl $3\; \backslash cdot\; 13^i$ und terminiert, sobald sie in der zweiten Komponente der vorherigen Tabelle gefunden wurde:
: Es ist also $i=2$ und $j=5$, damit ist $\backslash log\_\{11\}\; 3\; =\; 2\backslash cdot\; 6\; +\; 5\; =\; 17$.

       VIDEO-NEWS UND ANGEBOTE