Cryptography Reference
In-Depth Information
gilt:
J
n
(
x
e
mod
n
)=J
n
(
x
)
für alle
x
∈
Z
n
,
(6.4.4)
und
=
φ
(
n
)
2
n
=
pq
−
p
−
q
+1
Prob
x ←
Z
n
{
J
n
(
x
)=1
}
=Prob
x ←
Z
n
{
J
n
(
x
)=
−
1
}
,
(6.4.5)
2
n
=
p
+
q
−
1
pq
Prob
x ←
Z
n
{
J
n
(
x
)=0
}
.
(6.4.6)
Beweis.
Zum Beweis von (6.4.4) überlegen wir uns zunächst, dass
e
ungerade ist: Da
p
eine ungerade Primzahl ist, ist
p −
1
gerade. Weil
m
=(
p −
1)(
q −
1)
gilt, ist auch
m
gerade. Definitionsgemäß ist
e
∈
Z
∗
m
,alsoggT
(
e, m
)=1
, was impliziert, dass
e
ungerade
ist, d. h.,
e
=2
·
f
+1
für ein
f
∈
Z
. Daraus ergibt sich für alle
x
∈
Z
n
:
J
n
(
x
e
mod
n
)=J
n
(
x
e
)
=(J
n
(
x
))
e
=(J
n
(
x
))
2
f
+1
=(J
n
(
x
))
2
f
·
J
n
(
x
)
= ((J
n
(
x
))
2
)
f
·
J
n
(
x
)
=J
n
(
x
)
.
Dabei ist jede dieser Umformungen ein einfacher arithmetischer Schritt oder durch Lem-
ma 6.3.5 und 6.3.6 gerechtfertigt.
Zum Beweis von (6.4.6) erinnern wir uns zunächst an Lemma 6.3.5, aus dem sofort
folgt:
{
x
∈
Z
n
|
J
n
(
x
)=0
}
=
}
=
{
0
}∪{p,
2
p,
3
p,...,
(
q −
1)
p}∪{q,
2
q,
3
q,...,
(
p −
1)
q} .
{
x
∈
Z
n
|
p
|
x
oder
q
|
x
Da alle drei Mengen paarweise disjunkt sind und damit ihre Vereinigung
p
+
q
−
1
Elemente
besitzt, folgt (6.4.6).
Aus Lemma 6.3.5 folgt auch:
{x ∈
Z
n
|
J
n
(
x
)
∈{−
1
,
1
}}
=
Z
n
. Wir zeigen noch, dass
H
1
und
H
−
1
definiert durch
H
c
=
{
x
∈
Z
n
|
J
n
(
x
)=
c
}
gleich groß sind; daraus folgt
Z
p
. Dann gilt
J
p
(
a
)=
a
p−
1
dann (6.4.5). Es sei nun
a
ein Erzeuger von
rmod
p
=1
,
2
also
J
p
(
a
)=
1
, wie bereits im Beweis von Satz 6.3.10 gezeigt. Weiterhin existiert
nach dem Chinesischen Restsatz ein
b ∈
Z
n
mit
b
mod
p
=
a
und
b
mod
q
=1
.Also
insbesondere
b
−
∈
Z
n
und
J
n
(
b
)=J
p
(
a
)
·
J
q
(1) =
−
1
. Die Abbildungen
h
1
:
H
1
→
H
−
1
∈
Z
n
und
h
−
1
:
H
−
1
→
H
1
definiert durch
x
→
xb
mod
n
sind also wohldefiniert. Wegen
b
gilt offensichtlich, dass
h
1
und
h
−
1
injektiv sind. Daher gilt
|H
1
|
=
|H
−
1
|
.
Aus Algorithmus 6.3 geht hervor, dass das Jacobi-Symbol ezient berechnet werden
kann. Lemma 6.4.2 besagt somit, dass es sich bei der Eigenschaft »hat Jacobi-Symbol
1
«