Asymmetrische Verschlüsselung - Moderne Kryptographie - page 146

Definition 6.3.2 (Jacobi-Symbol). Für jede ungerade Zahl n ∈ N mit Primfaktorzer-

legung i<r p α i und jedes a ∈ Z ist das Jacobi-Symbol von a und n ,dasmit J n ( a )

i

bezeichnet wird, definiert durch
J n ( a )=
i<r

L p i ( a ) α i . (6.3.3)

Insbesondere gilt J 1 ( a )=1 für alle a ∈ Z

, da, nach Konvention, ein leeres Produkt den

Wert 1 hat.

Hierbei ist zu beachten, dass J n ( a ) im Allgemeinen keinen Aufschluss darüber gibt, ob
a ein quadratischer Rest modulo n ist, wenn n zusammengesetzt ist (siehe Aufgabe 6.7.8).
Allerdings können wir Folgendes festhalten.

Lemma 6.3.5. Für jede ungerade Zahl n ∈ N und jedes a ∈ Z gilt:

.
2. J n ( a )=0 genau dann, wenn ggT ( a, n )

1. J n ( a ) ∈{− 1 , 0 , 1 }

=1 .

Aufgrund von Satz 6.3.8 wissen wir schon, dass sich J n ( a ) ezient berechnen lässt,
wenn n eine Primzahl ist. Es gilt aber sogar, dass sich J n ( a ) im Allgemeinen ezient
berechnen lässt. Dies ergibt sich aus dem folgenden Lemma und dem darauffolgenden
Satz, der das in Satz 6.3.9 formulierte quadratische Reziprozitätsgesetz auf das Jacobi-
Symbol erweitert. Im Beweis des Lemmas verwenden wir, dass für alle ungeraden Zahlen
n ∈ N

gilt (siehe auch Aufgabe 6.7.5):
( − 1) ( n− 1) / 2 =

1 , falls n mod 4=1

(6.3.4)

− 1 , falls n mod 4=3

und

( − 1) ( n 2 − 1) / 8 =

1 , falls n mod 8=1 oder 7
−

. (6.3.5)

1 , falls n mod 8=3 oder 5

Lemma 6.3.6. Es seien a, b ∈ Z und m, n ∈ N ungerade. Dann gilt:

J n (1) = 1 , (6.3.6)

1) ( n− 1) / 2 , J n ( − 1) = ( − (6.3.7)

1) ( n 2 − 1) / 8 ,

J n (2) = ( − (6.3.8)

J n ( a )=J n ( a mod n ) ,

(6.3.9)

J n ( a · b )=J n ( a ) · J n ( b ) , (6.3.10)

J m·n ( a )=J m ( a ) · J n ( a ) .

(6.3.11)

Beweis. Gleichung (6.3.6) folgt aus der Eigenschaft des Legendre-Symbols, dass nämlich
L p (1) = 1 ( p− 1) / 2 rmod p =1 trivialerweise für jede Primzahl p> 2 gilt. Bei (6.3.10) und
(6.3.9) ist die Situation analog: Es gilt L p ( a·b )=( a·b ) ( p− 1) / 2 rmod p ( ∗ =( a ( p− 1) / 2 rmod p ) ·
( b ( p− 1) / 2 rmod p )=L p ( a ) · L p ( b ) , wobei man sich ( ∗ ) mit Lemma 6.3.8 leicht klar macht.