Cryptography Reference
In-Depth Information
case a quadratic nonresidue modulo
b
. The relation
b
=0
is equivalent to
gcd(
a, b
)
=1
.
From the properties of the Legendre symbol we can conclude the following
about the Jacobi symbol:
(i)
a
c
=
c
c
, and if
b · c
=0
,then
bc
=
b
c
.
(ii)
a ≡ c
mod
b ⇒
b
=
b
.
(iii)
For odd
b>
0
we have
−
b
=(
1)
(
b
−
1)
/
2
,
b
=(
1)
(
b
2
−
1
)
/
8
,and
−
−
b
=1
(see (viii) above).
(iv)
For odd
a
and
b
with
b>
0
we have the reciprocity law (see (viii) above)
b
=(
−
1)
(
a
−
1)(
b
−
1)
/
4
.
b
|
a
|
From these properties (see the above references for the proofs) of the Jacobi
symbol we have the following algorithm of Kronecker, taken from [Cohe], Section
1.4, that calculates the Jacobi symbol (or, depending on the conditions, the
Legendre symbol) of two integers in a nonrecursive way. The algorithm deals with
apossiblesignof
b
, and for this we set
a
−
1
:= 1
for
a ≥
0
and
1
:=
−
1
for
a
−
a<
0
.
Algorithm for calculating the Jacobi symbol
b
of integers
a
and
b
1.
If
b
=0
, output 1 if the absolute value
|a|
of
a
is equal to 1; otherwise, output
0 and terminate the algorithm.
2.
If
a
and
b
are both even, output 0 and terminate the algorithm. Otherwise,
set
v ←
0
, and as long as
b
is even, set
v ← v
+1
and
b ← b/
2
.Ifnow
v
is even, set
k ←
1
; otherwise, set
k ←
(
−
1)
(
a
2
1
)
/
8
.If
b<
0
, then set
−
b
←−
b
.If
a<
0
, set
k
←−
k
(cf. (iii)).
3.
If
a
=0
, output 0 if
b>
1
, otherwise
k
, and terminate the algorithm.
Otherwise, set
v ←
0
, and as long as
a
is even, set
v ← v
+1
and
a ← a/
2
.
If now
v
is odd, set
k ←
(
−
1)
(
b
2
1
)
/
8
−
· k
(cf. (iii)).
4.
Set
k ←
(
−
1)
(
a
−
1)(
b
−
1)
/
4
· k
,
r ←|a|
,
a ← b
mod
r
,
b ← r
, and go to step
3 (cf. (ii) and (iv)).
The run time of this procedure is
O
log
2
N
, where
N ≥ a, b
represents
an upper bound for
a
and
b
. This is a significant improvement over what we
achieved with the Euler criterion. The following tips for the implementation of
the algorithm are given in Section 1.4 of [Cohe].
