Cryptography Reference
In-Depth Information
10.4.2 Reduktion auf Primzahlordnung
Wir reduzieren das DLP nun auf Gruppen von Primzahlordnung.
Lemma 10.5
Es sei G
p
ν
für eine Primzahl p und ein
=
g
eine endliche zyklische Gruppe mit
|
G
|
=
ν
∈
N
). Dann lässt sich das DLP in G auf
ν
-maliges Logarithmieren in Gruppen der
Ordnung p reduzieren.
Beweis.
Wir begründen die Behauptung mit Induktion nach
ν
. Der Fall
ν
=
1
g
p
ν −
=
ist klar. Die Behauptung gelte für
1. Es ist
U
:
nach Lemma 6.2 eine
p
ν
−
1
. Folglich ist
Untergruppe von
G
mit
|
U
|
=
|
G
/
U
|
=
p
,
G
/
U
=
gU
.Essei
y
g
y
U
. Dann gilt
ag
−
y
∈
∈
N
=(
)
=
∈
=
a
G
. Bestimme ein
y
mit
aU
gU
U
g
p
. Nach Induktionsvoraussetzung können wir
x
∈
N
durch
(
ν
−
1
)
-malig
es
Logarithmieren bestimmen mit
ag
−
y
g
y
+
xp
.
=
g
px
, und es gilt
a
=
Mit Lemma 10.5 ist das DLP in Gruppen der Ordnung
p
ν
auf
DLPs in Gruppen
der Ordnung
p
reduziert. In der Praxis führt man die Reduktion wie im Folgen-
den beschrieben durch.
Gegeben ist die zyklische Gruppe
G
ν
p
ν
,
p
prim,
=
g
mit
|
G
|
=
ν
∈
N
. Zu einem
∈
=
Log
g
(
)
Element
a
gesucht. Man schreibe
den gesuchten diskreten Logarithmus
x
in der
p
-adischen Darstellung als
G
ist der diskrete Logarithmus
x
a
1
p
ν−
1
,
x
0
,...,
x
=
+
+
···
+
∈{
−
}
x
x
0
x
1
p
x
0, . . . ,
p
1
.
ν−
ν−
1
Wir bestimmen nun der Reihe nach die Zahlen
x
0
,...,
x
ν−
1
aus der Gleichung
g
x
0
+
x
1
p
+
···
+
x
ν−
1
p
ν−
1
g
x
(
∗
)
=
a
, . .
=
a
und erhalten so die gesuchte Zahl
x
. Im Folgenden beachte man den Satz 6.9 von
Euler, wonach
g
p
ν
=
1 gilt.
Wir bestimmen
x
0
: Potenziere die Gleichung
g
x
a
mit
p
ν−
1
und erhalte
=
g
p
ν−
1
x
0
g
p
ν−
1
x
g
p
ν−
1
x
0
a
p
ν−
1
.
=
=
=
a
p
ν−
1
=
(
)
Berechne den diskreten Logarithmus
x
0
- man beachte, dass
das Element
g
p
ν
−
1
die Ordnung
p
hat. Damit ist
x
0
bestimmt.
Log
g
p
ν−
1
um zu
g
x
1
p
+
···
+
x
ν−
1
p
ν
−
1
Wir bestimmen
x
1
: Schreibe die Gleichung in
(
∗
)
=
ag
−
x
0
und potenziere diese Gleichung mit
p
ν−
2
und erhalte
g
p
ν−
1
x
1
ag
−
x
0
p
ν
−
2
g
p
ν−
1
x
1
=
=
.
a
p
ν
−
2
g
−
p
ν
−
2
x
0
Berechne den diskreten Logarithmus
x
1
=
Log
g
p
ν−
1
(
)
. Damit ist
x
1
bestimmt.
usw.
