Cryptography Reference
In-Depth Information
how to compute modular square roots modulo a prime. The easiest case is when
p
≡
(
)
3
mod 4
(
p
is then called a
Blum prime
). For these primes we have:
Proposition 2.15
is prime and a is a quadratic residue modulo
p, then the square roots of a modulo p are
If p
≡
3
(
mod 4
)
a
(
p
+
1
)/
4
mod
p.
±
Proof
Using Euler's criterion (Proposition 2.12) and the fact that
a
is a quadratic
residue modulo
p
,wehave
p
a
(
p
+
1
)/
4
2
a
(
p
+
1
)/
2
a
(
p
−
1
)/
2
(
±
)
≡
≡
a
·
≡
a
·
≡
a
(
mod
p
).
Observe that the argument used to prove the proposition does not work when
4 is an integer, which
is no longer true in this case. So we now describe an algorithm that computes square
roots modulo any odd prime.
If
p
is an odd prime, we may write
p
p
≡
1
(
mod 4
)
because we made use of the fact that
(
p
+
1
)/
2
s
t
with
t
odd and consider
A
−
1
=
=
a
t
mod
p
. Then
A
2
s
−
1
a
(
p
−
1
)/
2
by Euler's criterion, so we know
from Proposition 2.4 that the order of
A
is a divisor of 2
s
−
1
.Nowlet
h
≡
≡
1
(
mod
p
)
∈ Z
p
be
h
t
mod
p
. The order of
H
is a power of 2 by
a quadratic non-residue and
H
=
Proposition 2.4 and, since
H
2
s
−
1
h
2
s
−
1
t
h
(
p
−
1
)/
2
again by
Euler's criterion, we see that the order of
H
is exactly 2
s
. The order of its inverse
H
−
1
≡
≡
≡−
1
(
mod
p
)
∈ Z
p
is also 2
s
and hence
H
−
1
H
=
is the unique (cyclic) subgroup of
order 2
s
of the cyclic group
Z
p
, and it contains all the elements of
Z
p
whose order is a
Z
p
. Moreover,
A
is an even power of
H
−
1
because otherwise it would follow from Proposition 2.5
that
A
has the same order as
H
−
1
, namely 2
s
, in contradiction with the fact that, as
we have seen, the order of
A
divides 2
s
−
1
. Thus we see that there exists an integer
u
such that 0
H
−
1
and hence
A
is a power of
H
−
1
in
power of 2. In particular,
A
∈
2
s
−
1
and
A
H
−
2
u
a
t
≤
u
<
≡
(
mod
p
)
. Since
A
≡
(
mod
p
)
,thisis
equivalent to
a
t
H
2
u
≡
1
(
mod
p
)
and, multiplying this congruence by
a
, we obtain
a
(
t
+
1
)
H
2
u
a
. Now the terms on the right side of this congruence all have
even exponents and we find a square root of
a
modulo
p
by halving these exponents,
namely, by computing
a
(
t
+
1
)/
2
H
u
mod
p
(see [60]).
In order to complete the description of the square roots algorithm we need to
show how to find the quadratic non-residue
h
and how to find the integer
u
such that
A
≡
(
mod
p
)
H
−
2
u
. The first problem is very interesting because no deterministic
polynomial-time algorithms to find a quadratic non-residue modulo
p
are known.
10
It is easy, however, to describe a probabilistic polynomial-time algorithm that does
the job: just pick random elements in
≡
(
mod
p
)
Z
n
and use either Euler's criterion or Algorithm
2.7 to check whether they are quadratic non-residues. Since, as we have seen, exactly
one-half of the integers in
Z
p
are quadratic non-residues, the expected number of
trials until finding one of them is 2.
Thus, in order to complete the algorithm, it only remains to find the integer
u
satisfying the conditions explained above. We show how to do it in Algorithm 2.8:
10
As in the case of primitive roots, there is a deterministic polynomial-time algorithm under the
assumption that the
Extended Riemann Hypothesis
holds.
