Cryptography Reference
In-Depth Information
10.4.1 The Jacobi Symbol
We plunge right into this section with a definition: Let
p
=2
be a prime number
and
a
an integer. The
Legendre symbol
p
(say “
a
over
p
”) is defined to be 1 if
a
is a quadratic residue modulo
p
and to be
−
1
if
a
is a quadratic nonresidue
modulo
p
.If
p
is a divisor of
a
,then
p
:= 0
. As a definition the Legendre
symbol does not seem to help us much, since in order to know its value we
have to know whether
a
is a quadratic residue modulo
p
. However, the Legendre
symbol has properties that will allow us to do calculations with it and above all to
determine its value. Without going too far afield we cannot go into the theoretical
background. For that the reader is referred to, for example, [Bund], Section 3.2.
Nonetheless, we would like to cite some of these properties to give the reader an
idea of the basis for calculation with the Legendre symbol:
≡ a
(
mod
p
)
is
1+
p
.
(i)
The number of solutions of the congruence
x
2
(ii)
There are as many quadratic residues as nonresidues modulo
p
, namely
(
p
−
1)
/
2
.
p
=
p
.
(iv)
The Legendre symbol is multiplicative:
a
p
=
p
p
.
(iii)
a ≡ b
(
mod
p
)
⇒
i
p
=0
.
p
−
1
(v)
i
=1
p
(
mod
p
)
(Euler criterion).
(vi)
a
(
p
−
1)
/
2
≡
=
p
, we have
q
=(
1)
(
p
−
1)(
q
−
1)
/
4
p
(law of
(vii)
For an odd prime
q
,
q
−
quadratic reciprocity of Gauss).
(viii)
−
p
=(
−
1)
(
p
−
1)
/
2
,
p
=(
−
1)
(
p
2
−
1
)
/
8
,
p
=1
.
The proofs of these properties of the Legendre symbol can be found in the
standard literature on number theory, for example [Bund] or [Rose].
Two ideas for calculating the Legendre symbol come at once to mind: We
can use the Euler criterion (vi) and compute
a
(
p
−
1)
/
2
(
mod
p
)
. This requires
a modular exponentiation (an operation of complexity
O
log
3
p
). Using the
reciprocity law, however, we can employ the following recursive procedure, which
is based on properties (iii), (iv), (vii), and (viii).
Recursive algorithm for calculating the Legendre symbol
p
of an integer
a
and an odd prime
p
1.
If
a
=1
,then
p
=1
(property (viii)).
