Pohlig-Hellman-Algorithmus - LinkFang.de





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-Algorithmus kann der diskrete Logarithmus in einer zyklischen Gruppe berechnet werden.

Die Relevanz dieses Verfahrens liegt darin, dass der Rechenaufwand nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Nachteilig ist, dass für dieses Verfahren eine Primfaktorzerlegung der Gruppenordnung bekannt sein muss. Solch eine Primfaktorzerlegung ist im Allgemeinen jedoch nur sehr schwer zu bestimmen.

Mathematischer Hintergrund

Sei [math]G[/math] eine zyklische Gruppe der Ordnung [math]n[/math], wobei die Faktorisierung von [math]n[/math] bekannt und [math]p[/math] der größte Faktor von [math]n[/math] sei. Der diskrete Logarithmus in der Gruppe [math]G[/math] lässt sich dann mittels Silver-Pohlig-Hellman in [math]\mathcal O(\sqrt p)[/math] statt [math]\mathcal{O}(\sqrt n)[/math] Operationen berechnen. Dies geschieht in drei Schritten:

  1. Reduktion des Problems der Gruppe [math]G[/math] in zyklische Gruppen [math]G_{p^k}[/math] deren Ordnung [math]p^k[/math] ist, wobei [math]p^k[/math] ein Teiler von [math]n[/math] ist (die sich später hieraus ergebende Lösung ist eindeutig nach dem Chinesischen Restsatz).
  2. Reduktion von Gruppen mit Primzahlpotenzordnung in Gruppen mit Primordnung
  3. Zusammensetzen des Ergebnisses mittels des Chinesischen Restsatzes.

Der Algorithmus

Sei [math]G[/math] die zyklische Gruppe der Ordnung [math]n[/math], [math]g[/math] ein Generator von [math]G[/math] und [math]h \in \left\langle g \right\rangle [/math]. Weiter sei [math]n=\Pi_{i=1}^{k}q_i^{e_i}[/math] die Primfaktorzerlegung von [math]n[/math].

Der Algorithmus ist nun in zwei Schritten angegeben. Zuerst folgt eine Version für Gruppen, deren Ordnung einer Primzahlpotenz entspricht. Dieser kann im Folgenden als Unteralgorithmus im Allgemeinen Pohlig-Hellman verwendet werden.

Prime-Power-Pohlig-Hellman

Die Gruppenordnung sei [math]n=q^e[/math], wobei [math]q[/math] eine Primzahl ist. Zur Bestimmung des diskreten Logarithmus in den Untergruppen wird der Babystep-Giantstep-Algorithmus von Shanks verwendet.

Eingabe: [math]g, q, e, h[/math]
Ausgabe Der diskrete Logarithmus [math]a:= \log_g(h)[/math]
  1. [math] u\leftarrow h^{q^{e-1}}, \hat g \leftarrow g^{q^{e-1}}[/math]
  2. [math] a_0 \leftarrow [/math] Shanks([math]\hat g, q, u[/math]), [math]a\leftarrow a_0, \hat h\leftarrow h\cdot g^{-a_0}[/math]
  3. for [math]i\leftarrow 1[/math] to [math]e-1[/math] do
    1. [math]u\leftarrow \hat h^{q^{e-i-1}}[/math]
    2. [math]a_i \leftarrow [/math]Shanks([math]\hat g, q, u[/math])
    3. [math] a\leftarrow a + a_iq^i, \hat h\leftarrow \hat h\cdot g^{-a_iq^i}[/math]
  4. return [math]a[/math]

In diesem Algorithmus wird verwendet, dass der diskrete Logarithmus [math]a=\log_g(h)[/math] in der folgenden Form geschrieben werden kann: [math]\log_g(h) = a = \sum_{i=0}^{e-1}a_iq^i, 0\leq a_i \leq q-1, i=0,\dots e-1[/math]. Aufgrund der vorgenommenen Beschränkungen ist diese Darstellung eindeutig.

Allgemeiner Pohlig-Hellman

Eingabe: [math]g, h, n, q_1, \dots, q_k, e_1 \dots e_k[/math]
Ausgabe Der diskrete Logarithmus [math]a:= \log_g(h)[/math]
  1. for [math]i\leftarrow 1[/math] to [math]k[/math] do
    1. [math] n_i \leftarrow n/q_i^{e_i}, g_i\leftarrow g^{n_i}, h_i \leftarrow h^{n_i}[/math]
    2. [math] c_i \leftarrow[/math] Prime-Power-Pohlig-Hellman([math]g_i, q_i, e_i, h_i[/math])
  2. Berechne für [math]i=1,\dots k[/math] mit dem Chinesischen Restsatz [math]c=c_i \mod q_i^{e_i}[/math].
  3. return [math]c[/math].

Referenzen

  1. S. Pohlig and M. Hellman. "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Trans. Information Theory 24, 1978, Seiten. 106-110.
  2. V. Shoup. "A Computational Introduction to Number Theory and Algebra", Cambridge University Press, 2007, http://shoup.net/ntb/ , Seite 325ff.

Kategorien: Zahlentheoretischer Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Pohlig-Hellman-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.