imported>SchlurcherBot: Bot: http → https

2026-01-22T04:43:41Z

Bot: http → https

Neue Seite

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 [[Diskreter Logarithmus|diskrete Logarithmus]] in einer [[Zyklische Gruppe|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> [[Gleitkommaoperation|Operationen]] berechnen. Dies geschieht in drei Schritten:

# 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 [[Chinesischer Restsatz|Chinesischen Restsatz]]).
# Reduktion von Gruppen mit Primzahlpotenzordnung in Gruppen mit Primordnung
# 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 [[Erzeuger einer Gruppe|Erzeuger]] 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 [[Untergruppe|Untergruppen]] wird der [[Babystep-Giantstep-Algorithmus|Babystep-Giantstep-Algorithmus von Shanks]] verwendet.

:'''Eingabe:''' <math>g, q, e, h</math>
:'''Ausgabe:''' Der diskrete Logarithmus <math>a:= \log_g(h)</math>
:# <math> u\leftarrow h^{q^{e-1}}, \hat g \leftarrow g^{q^{e-1}}</math>
:# <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>
:# '''for''' <math>i\leftarrow 1</math> '''to''' <math>e-1</math> '''do'''
:## <math>u\leftarrow \hat h^{q^{e-i-1}}</math>
:## <math>a_i \leftarrow </math>'''Shanks'''(<math>\hat g, q, u</math>)
:## <math> a\leftarrow a + a_iq^i, \hat h\leftarrow \hat h\cdot g^{-a_iq^i}</math>
:# '''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>
:# '''for''' <math>i\leftarrow 1</math> '''to''' <math>k</math> '''do'''
:## <math> n_i \leftarrow n/q_i^{e_i}, g_i\leftarrow g^{n_i}, h_i \leftarrow h^{n_i}</math>
:## <math> c_i \leftarrow</math> '''Prime-Power-Pohlig-Hellman'''(<math>g_i, q_i, e_i, h_i</math>)
:# Berechne für <math>i=1,\dots k</math> mit dem Chinesischen Restsatz <math>c=c_i \mod q_i^{e_i}</math>.
:# '''return''' <math>c</math>.

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

[[Kategorie:Zahlentheoretischer Algorithmus]]

Pohlig-Hellman-Algorithmus - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https