Cryptography Reference
In-Depth Information
Beispiel
In
Z
15
=
{
}
s
ind
d
ie Ele
mente 1 und 4 die
Q
uadrate. Das
Element
1 h
at d
ie
Quadratwurzeln 1, 4, 11, 14 und das Element 4 die Quadrat-
wurzeln 2, 7, 8, 13.
1, 2, 4, 7, 8, 11, 13, 14
Z
15
genau vier Wurzeln hat.
Es ist kein Zufall, dass jedes Quadrat in
Lemma 9.1
E
s sei n
=
···
p
1
p
t
mit verschiedenen ungeraden Primzahlen p
1
,...,
p
t
. Ein Element
∈
Z
n
besitzt keine oder genau
2
t
Quadratwurzeln.
a
Z
n
mit
Z
p
1
×···×
Z
p
t
B
ewei
s.
Wege
n
Lemma 7.5 können wir
identifizieren. Ist
)
∈
Z
p
1
×···×
Z
p
t
eine Q
u
adratw
u
rzel von
a
=(
=(
)
b
b
1
,...,
b
t
a
1
,...,
a
t
,so
is
t offenba
r
jede
s
Eleme
n
t von
W
:
=
{
(
±
b
1
,...,
±
b
t
)
}
eine Quadratwurzel von
)
∈
Z
p
1
×···×
Z
p
t
=(
a
. Ist nun
c
c
1
,...,
c
t
eine weitere Quadratwurzel von
, so ist
c
i
eine Nu
l
lstelle des Polynoms
X
2
a
=(
a
1
,...,
a
t
)
−
a
i
über dem Körper
=
=
±
=
Z
p
i
für alle
i
1, . . . ,
t
. Somit ist
c
i
b
i
für alle
i
1, . . . ,
t
(siehe Satz 3.9), d.
h.
2
t
.
c
∈
W
. Damit ist
W
die Menge aller Quadratwurzeln, und es gilt
|
W
|
=
Bemerkung
Wie der Beweis zeigt, erhält man die Qu
a
dratwurzeln
b
modulo
n
von
a
folgen-
dermaßen aus den Quadra
t
wurze
ln
von
a
i
modulo
p
i
für
i
=
1, . . . ,
t
:
W
. Es gilt folglich
b
i
≡
Gegeben ist ein Element
(
b
1
,...,
b
t
)
∈
a
i
(
mod
p
i
)
für
=
∈
Z
i
1,...,
t
. Bestimme mit dem chinesischen Restsatz 7.4 ein Element
b
mit
≡
(
)
=
b
b
i
mod
p
i
für
i
1, . . . ,
t
.
Es ist dann
b
eine Quadratwurzel von
a
modulo
n
.
Wir halten für spätere Zwecke eine einfache Folgerung fest.
Korollar 9.2
Es sei n
=
···
p
1
p
t
mit verschiedenen ungeraden Primzahlen p
1
,...,
p
t
. Dann existie-
ren genau
ϕ
(
n
)
Z
n
.
2
t
Quadrate in
Beweis.
Wir betrachten die Abbildung
q
:
Z
n
→
Z
n
.
a
2
→
a
∈
Z
n
hat nach Lemma 9.1 genau 2
t
Quadratwurzeln, d.
h
.
Jedes Quadrat
b
q
−
1
2
t
.Da
Z
n
die disjunkte Vereinigung von Mengen der Form
q
−
1
|
(
)
|
=
(
)
b
b
Z
n
Z
n
:
mit einem Quadrat
b
in
ist, erhalten wir für die Anzahl der Quadrate in
|
Z
n
|
)
|
=
ϕ
(
n
)
(
Z
n
)
|
=
|
q
.
2
t
q
−
1
|
(
b
Das ist die Behauptung.
