DDiskrete Logarithmen - Kryptologie - page 185

Bemerkung
Auch bei dies er modifizierten Version ist der Rechenaufwand bei Pollards

-

( |

Methode O wegen des Geburtstagsparadoxons. Es gibt weitere Modifi-

kationen, die in der Praxis etwas schneller laufen (siehe [7, § 8.5]). Der Vorteil
von Pollards

G

| )

-Methode gegenüber dem Baby-Step-Giant-Step-Algorithmus von
Shanks liegt im sehr geringen Speicherbedarf.

10.4 Die Reduktion nach Silver-Pohlig-Hellman

| |

Auch wenn G beim ElGamal-Verfahren sehr groß ist, kann das DLP durch Pol-

lards -Methode oder den Baby-Step-Giant-Step-Algorithmus von Shanks sehr

einfach zu lösen sein. Das liegt daran, dass das DLP eventuell auf Gruppen klei-
ner Ordnung reduziert werden kann. Sind nämlich p 1 ,..., p n die Primteiler von
|

, so lässt sich das DLP auf Gruppen von der Ordnung p 1 ,..., p n reduzieren.
Will man also etwa vor den Algorithmen von Shanks oder Pollard sicher sein, so
sollte der größte Primteiler von

G

|

sehr groß sein. Wir behandeln diese Reduktion
in diesem Abschnitt. Wir benötigen dazu ein Lemma aus der Gruppentheorie.

|

G

|

Lemma 10.3
Ist G =

g eine endliche zyklische Gruppe der Ordnung n, so ist G zur additiven

Gruppe Z n isomorph.

Beweis. Wir betrachten den surjektiven Homomorphismus

: Z →

G

Φ .

g k k

→

Wegen o

(

g

)=

n ist n Z der Kern von . Nach dem Homomorphiesatz auf Sei te

Φ

Z = = Z 150 gilt somit Z n / n G .

10.4.1 Reduktion auf Primzahlpotenzordnung

Wir reduzieren das DLP in einem ersten Schritt auf Gruppen von Primzahlpo-
tenzordnung. Dazu beachten wir, dass wir nach den Lemmata 7.3 und 10.3 jede
zyklische Gruppe G mit

p ν 1 p ν

|

G

| =

n

= ···

(kanonische Primfaktorzerlegung)

als ein direktes Produkt

= ×···× G G 1 G

mit zyklischen Gruppen G 1 ,..., G mit paarweise teilerfremden Ordnungen

p ν 1 ,..., p ν | | = |

| =

G 1 G schreiben können. Wir führen die Reduktion für den

Fall 2 durch, der allgemeine Fall folgt hieraus induktiv.

Ist g 1 bzw. g 2 ein erzeugendes Element von G 1 bzw. G 2 , wobei die Gruppenord-
nungen

=

|

G 1

|

und

|

G 2

|

teilerfremd sind, so ist offenbar g

=(

g 1 , g 2

)

ein erzeugen-

des Element von G 1

×

G 2 . Es gilt: