Cryptography Reference
In-Depth Information
−
m
if m
n
=
(
−
)
(
n
−
1
)(
m
−
1
)/
4
m
=
≡
n
≡
3
(
mod 4
)
m
ot her wi se
1
.
Exercise 2.44
Use quadratic reciprocity to characterize the odd primes
p
such that
5 is a quadratic residue modulo
p
.
Remarks 2.8
1. When
n
=
p
is prime, part (i) of Theorem 2.24 tells us that whether
−
1isa
∈ Z
p
is a square) depends only on the
congruence class of
p
modulo 4 and, similarly, part (ii) says that the question
whether 2 is a square depends only on the congruence class of
p
modulo 8.
2. We mentioned above that quadratic reciprocity can be used to compute the Legen-
dre symbol and hence to determine whether an integer
a
is a square modulo a
prime
p
. This is done by using part (iii) of Theorem 2.24 to repeatedly flip the
Jacobi symbol, reducing the top number modulo the bottom number after each
flip (and pulling out powers of 2 by means of part (ii) of the theoremwhenever the
top number obtained after the reduction is even). As in the Euclidean algorithm,
these numbers decrease rapidly in size which gives a very efficient algorithm. In
the next example we show how this works.
square modulo
p
(or, equivalently,
p
−
1
Example 2.30
We determine whether 41069779796933 is a quadratic residue mod-
ulo 673275095033 (in this example both numbers are prime). The steps applied are
the following:
•
If both numbers are odd and the top number is greater than the bottom one, we
replace the top number by the result of reducing it modulo the bottom number.
•
If the top number is even, we use part (ii) of Theorem 2.24 to pull out the largest
power of 2 that divides it.
•
If both numbers are odd and the top number is smaller than the bottom one, we
use part (iii) of Theorem 2.24 to interchange the position of both numbers.
We then have the following computation, where we only point out the use of each of
the previous three steps the first time that they are used:
41069779796933
673275095033
=
(reducing the top number modulo the bottom number)
673274094953
673275095033
=
=
(by (iii) since the top number is congruent to 1 modulo 4)
673275095033
673274094953
1000080
673274094953
2
4
62505
673274094953
·
=
=
=
62505
673274094953
673274094953
62505
49838
62505
2
24919
62505
·
=
(
by (ii)
)
=
=
=
24919
62505
62505
24919
12667
24919
24919
12667
12252
12667
=
=
=
=−
=−
