Cryptography Reference
In-Depth Information
2.
If
a
is even, then
p
=(
1)
(
p
2
−
1
)
/
8
a/
2
p
(properties (iv), (viii)).
−
3.
If
a
=1
and
a
=
q
1
···q
k
is the product of odd primes
q
1
,...,q
k
, then
a
p
=
q
i
p
.
k
i
=1
For each
i
we compute
q
i
p
=(
1)
(
p
−
1)(
q
i
−
1)
/
4
p
mod
q
i
q
i
−
by means of steps 1 through 3 (properties (iii), (iv), and (vii)).
Before we examine the programming techniques required for computing the
Legendre symbol we consider a generalization that can be carried out without
the prime decomposition, such as would be required by the direct application
of the reciprocity law in the version above (vii), which for large numbers takes
an enormous amount of time (for the factoring problem see page 203). At that
point we will be able to fall back on a nonrecursive procedure: For an integer
a
and an integer
b
=
p
1
p
2
···
p
k
with not necessarily distinct prime factors
p
i
the
Jacobi symbol (or Jacobi-Kronecker, Kronecker-Jacobi, or Kronecker symbol)
b
is defined as the product of the Legendre symbols
p
i
:
a
b
a
p
i
,
:=
k
i
=1
where
2
:=
0
a
if
a
is even,
1
)
/
8
if
a
is odd
.
For the sake of completeness we set
1
:= 1
for
a ∈
Z
(
−
1)
(
a
2
−
,
0
:= 1
if
a
=
±
1
,and
0
:= 0
otherwise.
If
b
is itself an odd prime (that is,
k
=1
), then the values of the Jacobi
and Legendre symbols are the same. In this case the Jacobi (Legendre) symbol
specifies whether
a
is a quadratic residue modulo
b
, that is, whether there is a
number
c
with
c
2
a
mod
b
, in which case
b
=1
. Otherwise,
b
=
≡
−
1
(or
b
=0
if
a ≡
0mod
b
). If
b
is not a prime (that is,
k>
1
), then we have that
a
is a quadratic residue modulo
b
if and only if
gcd(
a, b
)=1
and
a
is a quadratic
residue modulo all primes that divide
b
, that is, if all Legendre symbols
p
i
,
i
=1
,...,k
,havethevalue
1
. This is clearly not equivalent to the Jacobi symbol
b
having the value
1
:Since
x
2
≡
2mod3
has no solution, we have
3
=
−
1
.
However, by definition,
9
=
3
3
=1
, although for
x
2
≡
2mod9
there
is likewise no solution. On the other hand, if
b
=
−
1
,then
a
is in every
