Cryptography Reference
In-Depth Information
Remark 2.7
Whether an integer
a
is a quadratic residue or a quadratic non-residue
depends only on the congruence class of
a
modulo
n
and the quadratic residues
correspond to the squares in the group
Z
n
∈
(
Z
n
)
2
x
2
∈ Z
n
}
(if
a
={
|
x
, we will
Z
n
or that
a
is a quadratic
not distinguish between saying that
a
is a square in
Z
15
residue). For example, in
={
1
,
2
,
4
,
7
,
8
,
11
,
13
,
14
}
we see that the squares
1
2
4
2
11
2
14
2
are 1 and 4. In fact, we have that in this group 1
=
=
=
=
2
2
7
2
8
2
13
2
and 4
=
=
=
=
so that each of these squares has exactly
four square roots.
Example 2.28
We do a slightly larger example using Maple (much larger examples
are possible but it is not practical to print the results!). Taking into account that if
b
2
2
=
a
then also
(
−
b
)
=
a
(where
−
b
is the opposite of
b
in
Z
n
) we see that in
Z
n
(and hence all the quadratic residues modulo
n
), we only have to compute the squares of the elements 1
order to compute all the squares in
,
2
,...,
n
/
2
(because
Z
n
are opposites of some of these and, in fact, as seen
in the preceding remark, there can even be different elements among them with the
same square). Then the function that computes the quadratic residues in
the remaining elements of
Z
n
is the
following:
> qr := n -> sort(ListTools:-MakeUnique(
map(x -> x&ˆ2 mod n, select(x -> evalb(igcd(x,n)=1), [$1..floor(n/2)])))):
which, when applied to
n
=
187
=
11
·
17, gives:
> qr(187);
[1, 4, 9, 15, 16, 25, 26, 36, 38, 42, 47, 49, 53, 59, 60, 64, 67, 69, 70, 81,
86, 89, 93, 100, 103, 104, 111, 115, 135, 137, 144, 152, 155, 157, 166, 168,
169, 174, 179, 185]
Z
187
there are exactly 40 squares:
We see that in
> nops(%);
40
Z
187
is:
while the order of the group
> numtheory:-phi(187);
160
As in the previous remark we see that exactly one-fourth of the elements in the
group are squares and this has not happened by chance. It is a consequence of the
fact that, as we will see later, when
n
is, as in this case, a product of two distinct
odd primes, each square has four square roots. For example, in
Z
187
, the four square
,
,
,
roots of 1 are 1
67
120
186 (see Exercise 2.40 below).
Exercise 2.40
Write a Maple procedure that uses brute force to find all the square
roots of a quadratic residue in the preceding example (and in similar examples; we
will later give a more efficient algorithm to extract modular square roots). Use it to
compute the four square roots of 1 and the four square roots of 115 in
Z
187
.
