Cryptography Reference
In-Depth Information
3.3.7.1
Prime
Z
p
,
Z
p
=
For every prime number
p
,
is
the multiplicative group. In this group, quadratic residuosity is a comparable simple
construct that is not too different from integer arithmetic. For example, it can be
shown that any polynomial of degree two has at most two solutions, and that in
Z
p
,
+
,
·
is a field and
·
with
Z
p
\{
0
}
Z
p
every
x
∈
QR
p
has exactly two square roots modulo
p
(if
y
is one of them, then
the other is
y
). There are, however, also some things that are different
from integer arithmetic. For example, among integers, perfect squares are quite
sparse, and they get sparser and sparser for large
n
(i.e., there are only about
√
n
perfect squares in the interval [1
,n
]). Contrary to that, half of the elements of
−
y
=
p
−
Z
p
are quadratic residues (and elements of
QR
p
accordingly). In fact, the following
equation holds for every odd prime (i.e., for every prime
p>
2):
p
−
1
|
QR
p
|
=
2
Z
7
the elements
For example, in
{
1
,
2
,
3
,
4
,
5
,
6
}
can all be set to the power of
two to figure out quadratic residues:
x
123456
x
2
142241
Note that only 1, 4, and 2 occur on the second line and represent quadratic
residues accordingly. Consequently,
QR
7
=
Z
7
\
{
1
,
2
,
4
}
and
QNR
7
=
QR
7
=
{
3
,
5
,
6
}
.
25
Using the same algorithm, one can easily determine
QR
19
=
{
1
,
4
,
5
,
6
,
7
,
9
,
11
,
16
,
17
}
and
Z
19
\
QNR
19
=
QR
19
=
{
2
,
3
,
8
,
10
,
12
,
13
,
14
,
15
,
18
}
Even though it is known that half of the elements in
Z
p
are quadratic nonresidues modulo
p
,thereis
no deterministic polynomial-time algorithm known for finding one. A randomized algorithm for
finding a quadratic nonresidue is to simply select random integers
a ∈
Z
p
until one is found
(using, for example, Euler's criterion to decide whether a quadratic nonresidue has been found).
The expected number of iterations before a nonresidue is found is 2, and hence the algorithm takes
expected polynomial time.
25
