Cryptography Reference
In-Depth Information
3. Schritt.
Bestimme den diskreten Logarithmus
x
=
Log
g
(
a
)
wie folgt: Mit den
g
x
und (ii) in Lemma 6.1 (b):
=
Zahlen
s
und
t
aus dem 2. Schritt gilt wegen
a
g
t
a
s
g
sx
,d.h.
sx
=
=
≡
(
)
t
mod
n
.
Folglich ist das gesuchte
x
eine Lösung der Kongruenzgleichung
≡
(
)
sX
t
mod
n
.
Die Lösungsmenge dieser Kongruenzgleichung ist nach Korollar 4.19 die Menge
v
n
+
=
(
)
und
v
die ohne Einschränkung kleinste positive
Lösung der Kongruenzgleichung ist. Wir erhalten
v
wie in der Bemerkung nach
Korollar 4.19 geschildert mit dem euklidischen Algorithmus. Da der diskrete Lo-
garithmus
x
kleiner als
n
ist, findet man
x
unter den
d
Zahlen
d
Z
, wobei
d
ggT
s
,
n
n
d
,
v
2
n
n
d
.
v
,
v
+
+
d
,...,
v
+(
d
−
1
)
Enumeration, d. h. Bestimmen von
g
v
+
k
d
,
k
=
−
0, . . . ,
d
1, und Vergleichen des
Ergebnisses mit
a
liefert
x
.
Bemerkung
Falls
dgroß
sein sollte, so kann es durchaus effizienter sein, das Verfahren von
vorne zu beginnen, um ein
kleines d
zu erhalten, als die Enumeration durchzu-
führen.
Beispiel
Geg
e
ben ist die zyklische Gruppe
G
=
Z
13
=
2
. Es ist also
g
=
2, und es sei
a
=
9. Wir bestimmen
x
=
Log
g
(
a
)
mit Pollards
-Methode.
1. Schritt:
Wir wählen
=
{
}
=
{
}
=
{
}
G
1
:
1, 4, 7, 10
,
G
2
:
2, 5, 8, 11
,
G
3
:
3, 6, 9, 12
.
=
2. Schritt:
Wir bestimmen nun die Folgenglieder
x
1
,...,
x
i
,...,
x
j
, sodass
x
i
x
j
:
i
0
1
2
3
4
5
6
7
x
i
1
9
5
12
11
4
10
12
Stop!
α
i
0
1
1
2
2
4
5
6
β
i
0
0
1
2
3
6
6
6
Mit den Größen
i
=
3,
j
=
7,
α
i
=
2,
α
j
=
6,
β
i
=
2,
β
j
=
6
erhalten wir
s
4.
3. Schritt:
Als Lösungsmenge der Kongruenzgleichung
=
−
4 (bzw.
s
=
8) und
t
=
(
−
4
)
X
≡
4
(
mod 12
)
