Cryptography Reference
In-Depth Information
gilt:
J n ( x e mod n )=J n ( x )
für alle x
Z n ,
(6.4.4)
und
= φ ( n )
2 n
= pq
p
q +1
Prob
x ← Z n {
J n ( x )=1
}
=Prob
x ← Z n {
J n ( x )=
1
}
,
(6.4.5)
2 n
= p + q 1
pq
Prob
x ← Z n {
J n ( x )=0
}
.
(6.4.6)
Beweis. Zum Beweis von (6.4.4) überlegen wir uns zunächst, dass e ungerade ist: Da p
eine ungerade Primzahl ist, ist p − 1 gerade. Weil m =( p − 1)( q − 1) gilt, ist auch m
gerade. Definitionsgemäß ist e
Z m ,alsoggT ( e, m )=1 , was impliziert, dass e ungerade
ist, d. h., e =2
·
f +1 für ein f
Z
. Daraus ergibt sich für alle x
Z n :
J n ( x e mod n )=J n ( x e )
=(J n ( x )) e
=(J n ( x )) 2 f +1
=(J n ( x )) 2 f
· J n ( x )
= ((J n ( x )) 2 ) f
·
J n ( x )
=J n ( x ) .
Dabei ist jede dieser Umformungen ein einfacher arithmetischer Schritt oder durch Lem-
ma 6.3.5 und 6.3.6 gerechtfertigt.
Zum Beweis von (6.4.6) erinnern wir uns zunächst an Lemma 6.3.5, aus dem sofort
folgt:
{
x
Z n |
J n ( x )=0
}
=
}
= { 0 }∪{p, 2 p, 3 p,..., ( q − 1) p}∪{q, 2 q, 3 q,..., ( p − 1) q} .
{
x
Z n |
p
|
x oder q
|
x
Da alle drei Mengen paarweise disjunkt sind und damit ihre Vereinigung p + q
1 Elemente
besitzt, folgt (6.4.6).
Aus Lemma 6.3.5 folgt auch:
{x ∈ Z n | J n ( x ) ∈{− 1 , 1 }} = Z n . Wir zeigen noch, dass
H 1
und H 1
definiert durch H c =
{
x
Z n |
J n ( x )= c
}
gleich groß sind; daraus folgt
Z p . Dann gilt J p ( a )= a p− 1
dann (6.4.5). Es sei nun a ein Erzeuger von
rmod p =1 ,
2
also J p ( a )=
1 , wie bereits im Beweis von Satz 6.3.10 gezeigt. Weiterhin existiert
nach dem Chinesischen Restsatz ein b ∈ Z n mit b mod p = a und b mod q =1 .Also
insbesondere b
Z n
und J n ( b )=J p ( a )
·
J q (1) =
1 . Die Abbildungen h 1 : H 1
H 1
Z n
und h 1 : H 1
H 1 definiert durch x
xb mod n sind also wohldefiniert. Wegen b
gilt offensichtlich, dass h 1 und h 1 injektiv sind. Daher gilt
|H 1 | = |H 1 |
.
Aus Algorithmus 6.3 geht hervor, dass das Jacobi-Symbol ezient berechnet werden
kann. Lemma 6.4.2 besagt somit, dass es sich bei der Eigenschaft »hat Jacobi-Symbol 1 «
 
Search WWH ::




Custom Search