Bsgs

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 praktisch nicht durchführbar. Der Algorithmus stammt von Daniel Shanks.

Theorie

Gesucht sei der diskrete Logarithmus x: = logga 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 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:=\varphi(29)=28, da 29 eine Primzahl ist (hierbei ist \varphi 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:

  • BSGS — The abbreviation BSGS has two meanings, both related to group theory in mathematics:* Baby step giant step, an algorithm for solving the discrete logarithm problem * The combination of a base and strong generating set (SGS) for a permutation… …   Wikipedia

  • BSGS — Bachelor of Science in General Studies (Academic & Science » Academic Degrees) …   Abbreviations dictionary

  • Betriebssportgemeinschaft — A Betriebssportgemeinschaft (English: Company sports community) was an organizational form of sports clubs in East Germany. After World War II, the Allied Control Commission had dissolved all existing sports structures, including the dissolution… …   Wikipedia

  • Bachelor's degree — A bachelor s degree is usually an undergraduate academic degree awarded for a course or major that generally lasts for three, four, or in some cases and countries, five or six years. It may also be the name of a postgraduate degree, such as a… …   Wikipedia

  • Blue supergiant — Blue supergiants (BSGs) are supergiant stars (luminosity class I) of spectral type O or B.They are extremely hot and bright, with surface temperatures of between 20,000 to 50,000°C. They typically have 10 to 50 solar masses on the Hertzsprung… …   Wikipedia

  • Schreier-Sims algorithm — The Schreier Sims algorithm is an efficient method of computing a base and strong generating set (BSGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS …   Wikipedia

  • Strong generating set — Let G leq S n be a permutation group. Let : B = (eta 1, eta 2, ldots, eta r) be a sequence of distinct integers, eta i in { 1, 2, ldots, n } , such that the pointwise stabilizer of B is trivial (ie: let B be a base for G ). Define : B i =… …   Wikipedia

  • Kandyse McClure — Infobox actor name = Kandyse McClure imagesize = 150px caption = Kandyse McClure, with kind permission by Mrs. Louise Mason, The Kandyse McClure Team birthname = Candise McClure birthdate = 1980 birthplace = Durban location = South Africa… …   Wikipedia

  • Base (group theory) — Let G be a finite permutation group acting on a set Omega. A sequence :B = [eta 1,eta 2,...,eta k] of k distinct elements of Omega is a base for G if the only element of G which fixes every eta i in B pointwise is the identity element of G.We …   Wikipedia

  • Bautzen — Wappen Deutschlandkarte …   Deutsch Wikipedia

Share the article and excerpts

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