Cryptography Reference
In-Depth Information
,
p
is an odd prime, and
m
(
p
−
1)
/q
(2)
If
m
∈
N
≡
1 (mod
p
)
for all primes
q
(
p
−
1)
, then
m
is a primitive root modulo
p
.
Proof
. See page 600.
✷
∈
N
and
c
is an integer,
then
c
is called a
quadratic residue modulo
n
if there exists an integer
x
such
that
x
2
Of particular importance is the following notion. If
n
c
(mod
n
). The
least quadratic residue
of
c
modulo
n
is the reduction
of
c
modulo
n
via Definition A.18. If no such integer exists, then
c
is called a
quadratic nonresidue modulo
n
. The following symbol makes it easier to study
quadratic residues.
≡
Definition A.26
(
Legendre's Symbol)
If
c
∈
Z
and
p>
2
is prime, then
if
p
c
,
c
p
=
0
1
if
c
is a quadratic residue modulo
p
,
−
1
otherwise,
and
(
p
)
is called the
Legendre symbol
of
c
with respect to
p
.
Example A.7
Let
p
be an odd prime. Then
1 (mod
p
), then
c
p
=1
,
if
c
(
p
−
1)
/
2
≡
and
1 (mod
p
), then
c
p
=
if
c
(
p
−
1)
/
2
≡−
−
1
.
This is called Euler's Criterion for quadratic residuacity.
Theorem A.17
(
Properties of the Legendre Symbol
)
If
p>
2
is prime and
b,c
∈
Z
, then
(1)
c
p
c
(
p
−
1)
/
2
(mod
p
)
.
≡
(2)
b
p
c
p
=
bc
p
.
(3)
b
p
=
c
p
, provided
b
≡
c
(mod
p
)
.
Proof
. See [169, Theorem 4.28, page 171].
✷
Of central importance in the study of the Legendre symbol is the next major
result.
Search WWH ::
Custom Search