Cryptography Reference
In-Depth Information
Theorem A.18
(
The Quadratic Reciprocity Law
)
If
p
=
q
are odd primes, then
p
q
q
p
=(
1)
p
−
1
q
−
1
2
.
·
−
2
Equivalently,
q
p
=
p
q
if
p
3 (mod 4)
, and
q
p
=
p
q
otherwise.
−
≡
q
≡
Proof
. See [169, Theorem 4.36, pages 173 and 174].
✷
The following generalization of the Legendre symbol will be needed to discuss
certain attacks on RSA for instance, (see page 210).
Definition A.27
(
The Jacobi Symbol)
Let
n>
1
be an odd natural number with
n
=
j
=1
p
e
j
and the
p
j
are distinct primes. Then the
Jacobi symbol
of
a
with respect to
n
is given
by
where
e
j
∈
N
j
a
p
j
e
j
a
n
=
k
,
j
=1
for any
a
∈
Z
, where the symbols on the right are Legendre symbols.
The Jacobi symbol satisfies the following properties.
Theorem A.19
(
Properties of the Jacobi Symbol)
Let
m,n
∈
N
, with
n
odd, and
a,b
∈
Z
. Then
(1)
ab
n
=
a
n
b
n
.
n
=
b
if
a
(2)
a
≡
b
(mod
n
)
.
n
(3)
If
m
is odd, then
a
mn
=
a
m
a
n
.
(4)
−
=(
1
n
1)
(
n
−
1)
/
2
.
−
(5)
2
n
=(
1)
(
n
2
−
1)
/
8
.
−
(6)
If
gcd(
a,n
)=1
where
a
∈
N
is odd, then
a
n
n
a
=(
1)
a
−
1
n
−
1
2
,
·
−
2
which is the
quadratic reciprocity law for the Jacobi symbol
.
Proof
. See [169, Theorem 4.40, pages 175 and 176].
✷
Search WWH ::
Custom Search