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
≡