Cryptography Reference
In-Depth Information
Lemma 7.8
Es seien p
,
q
=
∈
N
=
2
verschiedene Primzahlen, und es sei v
so gewählt, dass k
:
ed
−
1
2
v
∈
N
ungerade ist. Dann gilt
)
mod
q
≥
ϕ
(
a
n
)
a
k
a
k
∈
Z
<
<
(
)=
(
)
mod
p
=
(
;1
a
n
, ggT
a
,
n
1,
o
o
.
2
Beweis.
Es seien
g
p
und
g
q
ganze Zahlen mit der Eigenschaft, dass
g
p
∈
Z
p
eine
Primitivwurzel modulo
p
und
g
q
∈
Z
q
eine solche modulo
q
sind, d. h., es gilt
g
q
=
Z
q
(zur Existenz siehe Satz 6.12).
Nach dem chinesischen Restsatz 7.4 hat das Kongruenzgleichungssystem
g
p
=
Z
p
und
≡
(
)
≡
(
)
X
g
p
mod
p
,
X
g
q
mod
q
∈
Z
+
eine Lösung
g
. Es ist damit
g
p
Z
eine Primitivwurzel modulo
p
und
eine Primitivwurzel modulo
q
.
1. Fall: o
g
+
q
Z
g
k
g
k
(
)
mod
p
>
(
)
mod
q
. Es seien
α ∈{
−
}
o
1, . . . ,
p
1
ungerade und
β
∈{
0, . . . ,
q
−
2
}
. Mit dem chinesischen Restsatz 7.4 erhalten wir zu
(
α
,
β
)
eine
∈{
−
}
Lösung
a
2, . . . ,
n
1
des Kongruenzgleichungssystems
g
α
(
g
β
(
(
∗
)
X
≡
mod
p
)
,
X
≡
mod
q
)
.
g
α
∈
Z
p
g
β
∈
Z
q
Wegen
a
=
und
a
=
sind
a
und
n
teilerfremd. Und wegen
2
v
g
k
g
k
(
)
≡
1
(
mod
p
)
(beachte den Satz 6.9 von Euler) ist
o
(
)
mod
p
eine Potenz
von 2. Da 2
α
, gilt mit Lemma 6.2:
a
k
g
k
)
α
)
mod
p
=
g
k
(
)
mod
p
=
((
(
)
mod
p
.
o
o
o
Damit erhalten wir (man beachte erneut Lemma 6.2):
a
k
g
k
)
β
)
mod
q
≤
g
k
g
k
a
k
o
(
)
mod
q
=
o
((
o
(
)
mod
q
<
o
(
)
mod
p
=
o
(
)
mod
p
.
Aufgrund der Tatsache, dass
g
eine Primitivwurzel modulo
p
und
q
liefert, er-
halten wir für
(
α
,
β
)
=(
α
α
∈{
β
,
β
)
mit
1, . . . ,
p
−
1
}
ungerade und
∈
{
−
}
0,...,
q
2
auch ein anderes
a
als Lösung zu dem Kongruenzgleichungssys-
tem in
(
∗
)
. Weil es insgesamt
(
p
−
1
)(
q
−
1
)
/2
=
ϕ
(
n
)
/2 verschiedene solche
(
α
β
)
ϕ
(
)
Paare
,
gibt, gibt es auch
n
/2 verschiedene solche Zahlen
a
.
(
g
k
)
mod
p
<
(
g
k
)
mod
q
. Dieser Fall geht analog zum ersten Fall.
2. Fall: o
o
g
k
g
k
3. Fall: o
(
)
mod
p
=
o
(
)
mod
q
. Es seien
α
∈{
1, . . . ,
p
−
1
}
,
β
∈{
1, . . . ,
q
−
1
}
mit
α
≡
β
(
)
α
β
mod 2
, d. h.,
und
seien nicht beide zugleich gerade oder ungerade,
und
a
∈{
2, . . . ,
n
−
1
}
sei eine Lösung des Systems in
(
∗
)
. Wie im 1. Fall folgt:
(
−
)(
−
)
=
ϕ
(
)
Die Zahlen
a
und
n
sind teilerfremd und es existieren
p
1
q
1
/2
n
/2
verschiedene solche
a
.
Falls 2
| β
α
gilt, so folgt 2
und damit (beachte Lemma 6.2):
a
k
g
k
)
β
)
mod
q
<
g
k
g
k
a
k
o
(
)
mod
q
=
o
((
o
(
)
mod
q
=
o
(
)
mod
p
=
o
(
)
mod
p
.
