Cryptography Reference
In-Depth Information
g 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.
Search WWH ::




Custom Search