Pohlig-Hellman-Algorithmus

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.

Inhaltsverzeichnis

Mathematischer Hintergrund

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

  1. Reduktion des Problems der Gruppe G in zyklische Gruppen G_{p^k} deren Ordnung pk ist, wobei pk ein Teiler von n 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 G die zyklische Gruppe der Ordnung n, g ein Generator von G und h \in \left\langle g \right\rangle . Weiter sei n=\Pi_{i=1}^{k}q_i^{e_i} die Primfaktorzerlegung von n.

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 n = qe, wobei q eine Primzahl ist. Zur Bestimmung des diskreten Logarithmus in den Untergruppen wird der Babystep-Giantstep-Algorithmus von Shanks verwendet.

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

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

Allgemeiner Pohlig-Hellman

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

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.

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 — ist der Familienname folgender Personen: Julius Pohlig (1842–1916), deutscher Ingenieur und Unternehmer Karl Pohlig (1864–1928), Pianist und Komponist Stephen Pohlig, Mathematiker Siehe auch: Pohlig Hellman Algorithmus …   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

  • 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

  • Richard Schroeppel — (2004) Richard C. Schroeppel (* 1948 nahe Chicago in Illinois) ist ein US amerikanischer Informatiker und Mathematiker, der sich mit Algorithmischer Zahlentheorie und Kryptographie beschäftigt. Schroeppel studierte am MIT, wo er 1968 seinen… …   Deutsch Wikipedia

Share the article and excerpts

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