Cryptography Reference
In-Depth Information
n
bezeichnen wir mit
QR(
n
)
. Sie bildet, wie man mit Hilfe von Lemma 6.3.1 leicht sieht,
für
n ≥
2
eine Untergruppe von
Z
n
. Die Menge aller quadratischen Nichtreste modulo
n
bezeichnen wir mit
QNR(
n
)
.
Wir werden später folgende Aussage zu quadratischen Resten benötigen.
Lemma 6.3.4.
Es sei
p>
2
eine Primzahl. Dann besitzt jeder quadratische Rest in
Z
p
genau zwei Wurzeln.
Beweis.
Es sei
a
∈
Z
p
mit
b
2
mod
p
=
a
. Offensichtlich gilt
(
−b
)
2
mod
p
=
b
2
mod
p
=
a
,da
(
−
1)
·
(
−
1)
mod
p
=1
. Außerdem gilt
∈
QR(
p
)
. Dann existiert ein
b
−b
mod
p
=
b
,
b
folgen, im
Widerspruch zu
p>
2
und
0
<b<p
. Damit sind
−b
mod
p
und
b
verschiedene Elemente
in
da sonst
2
·
b
mod
p
=0
und also
p
|
2
·
b
. Daraus würde aber
p
|
2
oder
p
|
Z
p
und
a
besitzt zwei Wurzeln.
Wir zeigen nun, dass
a
keine weiteren Wurzeln besitzt. Nehmen wir dazu an, dass
neben
b
auch
b
∈
Z
p
eine Wurzel von
a
ist. Dann gilt
b
2
mod
p
=
b
2
mod
p
=
a
und
damit
(
b
2
− b
2
)
mod
p
=(
b − b
)
·
(
b
+
b
)
mod
p
=0
. Es folgt, dass
p |
(
b − b
)
oder
p
(
b
+
b
)
gilt, also
(
b
b
)
mod
p
=0
oder
(
b
+
b
)
mod
p
=0
. Aber das bedeutet,
b
=
b
|
−
oder
b
=
−b
mod
p
.
Z
p
für eine Primzahl
p>
2
ein quadratischer Rest ist, lässt sich,
wie aus dem folgenden Satz hervorgeht, leicht bestimmen. Wir benutzen in dem Satz
eine modifizierte Variante des Reduzierens modulo einer gegebenen Zahl: Für
n>
2
und
a
Ob ein Element von
∈
Z
setzen wir
a
rmod
n
=
a
mod
n,
falls
a
mod
n<n/
2
,
a
mod
n − n,
sonst.
Nun lässt sich der gewünschte Satz formulieren.
Satz 6.3.8 (Eulertest).
Es sei
p>
2
eine Primzahl,
a
und
e
=
a
(
p−
1)
/
2
rmod
p
.
∈
Z
Dann gilt:
1.
e
.
2.
a ∈
QR(
p
)
genau dann, wenn
e
=1
.
3.
a
∈{−
1
,
0
,
1
}
∈
QNR(
p
)
genau dann, wenn
e
=
−
1
.
Beweis.
Zunächst gilt für jedes
a
mit
a
rmod
p
=0
, und damit
a
mod
p
=0
:
a
mod
p ∈
Z
p
. Also gilt auch
a
p−
1
mod
p
=1
nach dem kleinen Satz von Fermat, und damit
a
p−
1
rmod
p
=1
. Dann ist aber
a
(
p−
1)
/
2
mod
p
eine Wurzel von
1
in dem Körper
Z
p
.
Dort sind nach Lemma 6.3.4 aber
1
und
−
1
die einzigen Wurzeln von
1
. Daraus folgt die
erste Behauptung.
Für jedes
a
∈
Z
p
, genau dann, wenn ggT
(
a, p
)=
p
.
Letzteres ist aber äquivalent zu
e
=0
. Es reicht also, die zweite Behauptung zu zeigen.
Wenn
a
ein quadratischer Rest ist, dann gibt es
b ∈
Z
p
mit
b
2
mod
p
=
a
mod
p
,also
a
(
p−
1)
/
2
mod
p
=
b
p−
1
mod
p
=1
nach dem kleinen Satz von Fermat. Dann gilt aber
auch
a
(
p−
1)
/
2
rmod
p
=1
. Wir erhalten also die Implikation von links nach rechts.
Zum Beweis der umgekehrten Implikation sei
g
ein Erzeuger von
∈
Z
gilt ggT
(
a, p
)
=1
,also
a/
Z
p
,
i<p
1
und
a
mod
p
=
g
i
mod
p
. Angenommen,
a
(
p−
1)
/
2
rmod
p
=1
. Dann gilt
1=(
g
i
)
(
p−
1)
/
2
mod
p
=
−
