Cryptography Reference
In-Depth Information
Z p is partitioned into two equal-
size subsets QR p and QNR p (each subset comprises ( p
for p =19. Consequently, for every prime p> 2,
1) / 2 elements).
Euler's criterion (Theorem 3.9) can be used to efficiently decide whether an
Z p is a quadratic residue modulo p . We don't prove the criterion is this topic.
x
Z p ,
Theorem 3.9 (Euler's criterion) Let p be a prime number. For any x
x
QR p if and only if
x p 1
1(mod p ) .
2
If Euler's Criterion is not met, then
x p 1
≡−
1(mod p ) .
2
Hence, Euler's criterion provides a criterion to decide whether an element
Z p is a quadratic residue modulo p .If x ( p− 1) / 2
x
1(mod p ),then x
QR p ;
otherwise if x ( p− 1) / 2
QNR p . In either case, the result
of Euler's criterion is captured by the Legendre symbol . The Legendre symbol of x
modulo p is formally defined as follows:
≡−
1(mod p ),then x
x
p
= +1
if x
QR p
1
otherwise (i.e., if x
QNR p )
For p> 2, the Legendre symbol can be computed using Euler's criterion:
x
p
x p 1
(mod p )
2
Consequently, p
(mod p )=1and p
1 p 1
1) p 1
(
for every
2
2
prime p .
From Euler's criterion we see that
x
p
= y
p
for x
y (mod p ). Furthermore, we see that the Legendre symbol is multiplica-
tive, meaning that
Search WWH ::




Custom Search