Cryptography Reference
In-Depth Information
=
i
p
e
i
i
be odd. The
Jacobi symbol
is
a
n
Let
n
a
p
i
e
i
=
.
i
A further generalisation is the
Kronecker symbol
(
n
), which allows
n
to be even. This
is defined in equation (
25.4
), which is the only place in the topic that it is used.
Exercise 2.4.2
Show that if
p
is an odd prime then (
p
)
=
1 for exactly half the integers
1
≤
a
≤
p
−
1.
∈ N
∈ Z
Theorem 2.4.3
Let n
be odd and a
. The Legendre and Jacobi symbols satisfy the
following properties:
(
a
(mod
n
)
n
(
n
)
)
and
(
n
)
=
=
1
.
(Euler's criterion) If n is prime then
(
n
)
a
(
n
−
1)
/
2
=
(mod
n
)
.
(Multiplicative)
(
a
n
)
(
n
)(
n
)
for all a,b
=
∈ Z
.
(
−
n
)
1)
(
n
−
1)
/
2
. In other words
−
=
(
−
1
1
n
if n
≡
1(mod4)
=
−
1
otherwise.
(
n
)
1)
(
n
2
−
1)
/
8
. In other words
2
n
=
(
−
1
if n
≡
1
,
7(mod8)
=
−
1
otherwise.
(Quadratic reciprocity) Let n and m be odd integers with gcd(m, n)
=
1
. Then
n
m
1)
(
m
−
1)(
n
−
1)
/
4
m
n
.
=
(
−
In other words,
(
m
)
(
n
)
unless m
=
≡
n
≡
3(mod4)
.
Proof
See Section II.2 of [
313
], Sections 3.1, 3.2 and 3.3 of [
420
] or Chapter 6 of [
250
].
An important fact is that it is not necessary to factor integers to compute the Jacobi
symbol.
Exercise 2.4.4
Write down an algorithm to compute Legendre and Jacobi symbols using
quadratic reciprocity.
Exercise 2.4.5
Prove that the complexity of computing (
n
)is
O
(log(
m
) log(
n
)) bit opera-
tions.
Exercise 2.4.6
Give a randomised algorithm to compute a quadratic non-residue modulo
p
. What is the expected complexity of this algorithm?
Exercise 2.4.7
Several applications require knowing a quadratic non-residue modulo a
prime
p
. Prove that the values
a
in the following table satisfy (
p
)
=−
1.