Cryptography Reference
In-Depth Information
g
i·
p−
1
p
−
1
2
|
Z
p
|
mod
p
,also
=
p
−
1
|
i
·
, gemäß (6.3.1). Daraus folgt
2
|
i
. Dann könne
n
2
wir
g
i
=(
g
i/
2
)
2
schreiben. Damit ist
g
i
ein quadratischer Rest.
Der gerade bewiesene Satz führt zur folgenden Definition, die von Adrien-Marie Le-
gendre (* 18. September 1752 in Paris; † 10. Januar 1833 in Paris) zuerst getroffen wurde.
Definition 6.3.1 (Legendre-Symbol). Es sei
a
eine beliebige ganze Zahl. Für jede Prim-
zahl
p>
2
ist das
Legendre-Symbol
von
a
und
p
,dasmit
L
p
(
a
)
bezeichnet wird, definiert
durch
L
p
(
a
)=
a
(
p−
1)
/
2
rmod
p.
Eine äußerst wichtige Eigenschaft des Legendre-Symbols geht auf Carl Friedrich Gauß
(* 30. April 1777 in Braunschweig; † 23. Februar 1855 in Göttingen) zurück:
Satz 6.3.9 (quadratisches Reziprozitätsgesetz für Primzahlen).
Für Primzahlen
p, q >
2
gilt:
L
q
(
p
)=(
−
1)
p−
1
q−
1
2
L
p
(
q
)
.
2
Zum Abschluss beschreiben wir die quadratischen Reste modulo einer Primzahl
p
genau:
Satz 6.3.10.
Es sei
p>
2
eine Primzahl und
g
ein Erzeuger von
Z
p
.Danngilt:
|
QR(
p
)
|
=
|
QNR(
p
)
|
=(
p
−
1)
/
2
und
QR(
p
)=
{g
2
i
mod
p | i<
(
p −
1)
/
2
} ,
QNR(
p
)=
{g
2
i
+1
mod
p | i<
(
p −
1)
/
2
} .
Beweis.
Offensichtlich gilt
g
2
i
=(
g
i
)
2
, so dass definitionsgemäß
{g
2
i
mod
p | i<
(
p −
1)
/
2
}⊆
QR(
p
)
gilt, also insbesondere
|
QR(
p
)
|≥
(
p
−
1)
/
2
. Andererseits gilt
o
(
g
)=
p
−
1
,
1
, denn sonst würde
g
(
p−
1)
/
2
mod
p
=1
nach Satz 6.3.8 gelten, was
ein Widerspruch dazu wäre, dass
g
ein Erzeuger von
also
L
p
(
g
)=
−
Z
p
ist. Damit ist
QR(
p
)
eine echte
Z
p
mit mindestens
(
p
Untergruppe von
1)
/
2
Elementen. Aus Folgerung 6.3.2 erhalten
wir sogar die Gleichheit. Daraus wiederum ergibt sich auch
QNR(
p
)=
{g
2
i
+1
mod
p |
i<
(
p
−
−
1)
/
2
}
.
Jacobi-Symbol
Die Überlegungen zu quadratischen Resten modulo einer Primzahl haben zu der folgen-
den allgemeinen Definition geführt, die auf Carl Gustav Jacob Jacobi (* 10. Dezember
1804 in Potsdam, † 18. Februar 1851 in Berlin) zurückgeht und für uns in Zusammenhang
mit speziellen asymmetrischen Kryptoschemen wichtig sein wird.