Cryptography Reference
In-Depth Information
(iii) If p does not divide b then
ab
2
p
p
.
=
(iv)
p
1
and
−
p
)
(
p
−
1
)/
2
.
=
=
(
−
1
Proof
As we have already remarked, (i) is a straightforward consequence of the
definition. (ii) follows from Euler's criterion since
a
(
p
−
1
)/
2
b
(
p
−
1
)/
2
)
(
p
−
1
)/
2
·
≡
(
ab
1
2
(
mod
p
)
. (iii) is an immediate consequence of (ii). For (iv), observe first that 1
=
is always a quadratic residue and so
p
1. Finally,
−
p
)
(
p
−
1
)/
2
by
=
=
(
−
1
Euler's criterion.
Remarks 2.6
1. As a consequence of part (ii) of the preceding proposition, a product of two
elements of
Z
p
(where
p
is an odd prime) is a quadratic residue if and only if
either both factors are quadratic residues or both are quadratic non-residues. Also,
(ii) reduces the computation of the Legendre symbol of
a
to those of the Legendre
symbols of its prime factors but this does not give an efficient method to compute
the Legendre symbol because factoring
a
is usually difficult.
2. The fact that
−
p
)
(
p
−
1
)/
2
is obviously equivalent to:
=
(
−
1
1f
p
−
1
p
≡
1
(
mod 4
)
=
−
1f
p
≡
3
(
mod 4
).
Exercise 2.42
Write a Maple function that, given a positive integer
n
, finds the
smallest prime
p
such that
a
is a quadratic residue modulo
p
for all 1
n
.Use
it to find the smallest prime
p
whose least quadratic non-residue is greater than 50 and
compute the value of this quadratic non-residue. Perform a similar computation for
other small values of
n
(it has been conjectured that the least quadratic non-residue
modulo
p
is
O
≤
a
≤
but no deterministic algorithm which is polynomial on
the size of
p
is known to find a quadratic non-residue).
The most efficient method to compute the Legendre symbol
p
is obtained by
using a generalization called the
Jacobi symbol
:
(
ln
p
ln ln
p
)
Definition 2.28
Let
a
be an integer and
n
a positive odd integer with prime factor-
ization
n
. Then the
Jacobi symbol
n
is defined by:
=
i
=
1
p
e
i
i
a
p
i
e
i
a
n
r
=
,
i
=
1
where the symbols on the right side are Legendre symbols and we define
1
=
1.
