Cryptography Reference
In-Depth Information
QR
n
and
QN
n
the sets of quadratic residues and quadratic
We will denote by
Z
n
, respectively; note that
QR
n
is the same as the set of the squares
non-residues in
(
Z
n
)
2
which is, clearly, a subgroup of
Z
n
:
Z
n
.
Exercise 2.41
Let
n
>
1 be an integer. Prove that
QR
n
is a subgroup of
Z
p
={
We will be especially interested in the set of squares
QR
p
of
1
,
2
,...,
p
−
1
2. Observe that 1 is always a quadratic residue and, moreover,
modulo a prime
p
its only square roots are
}
for an odd prime
p
>
±
1. This is because they are zeros of the
polynomial
x
2
which, as we have seen, are at most two. More generally,
the same argument shows that an element of
−
1
∈ Z
p
[
x
]
Z
p
has either two square roots (if it is a
quadratic residue) or none (if it is a quadratic non-residue). Next we show that
QR
p
and
QN
p
have the same number of elements:
|
QR
p
|=|
QN
p
|=
(
−
)/
Proposition 2.11
Let p be an odd prime. Then,
p
1
2
.
∈ Z
p
and, as we have already
remarked,
a
has precisely two square roots that must be
b
and
∈ Z
p
b
2
for some
b
Proof
If
a
is a square then
a
=
−
b
. If we consider the
: Z
p
→
QR
p
, given by
sq
x
2
, we see that each quadratic
squaring function
sq
(
x
)
=
Z
p
, from which the result follows.
residue is mapped onto by two elements of
Z
p
are precisely the elements
that can be written in the form
g
i
with
i
even (for, in that case,
g
i
∈ Z
p
is a generator, then the squares in
Remark 2.8
If
g
g
i
/
2
2
). In
=
(
±
)
Z
p
particular, we see that a generator of
is always a quadratic non-residue.
A convenient notation used to identify when an integer is a quadratic residue
modulo
p
is given by the Legendre symbol which we now define:
2 a prime. The
Legendre symbol
p
Definition 2.27
Let
a
be an integer and
p
>
is defined by:
⎧
⎨
a
p
0f
p
|
a
=
+
1f
a
is a quadratic residue mod
p
⎩
−
1f
a
is a quadratic non-residue mod
p
.
Example 2.29
We will see how the Legendre symbol can be efficiently computed;
Maple does it with the function
numtheory:-legendre
which can be used to
find quadratic residues and quadratic non-residues modulo primes. More generally,
the function
numtheory:-quadres
can be used to search for quadratic residues
even when the modulus is not prime: like the Legendre symbol this function takes
the value
1 on quadratic non-residues. Let
us consider the prime 101 and compute the quadratic residues in
+
1 on quadratic residues and the value
−
Z
101
:
> qr101 := select(x -> evalb(numtheory:-quadres(x, 101) = 1), {$1 .. 100})
{1, 4, 5, 6, 9, 13, 14, 16, 17, 19, 20, 21, 22, 23, 24, 25, 30, 31, 33, 36,
37, 43, 45, 47, 49, 52, 54, 56, 58, 64, 65, 68, 70, 71, 76, 77, 78, 79, 80,
81, 82, 84, 85, 87, 88, 92, 95, 96, 97, 100}
