Cryptography Reference
In-Depth Information
2.9 Square roots modulo
p
There are a number of situations in this topic that require computing square roots modulo a
prime. Let
p
be an odd prime and let
a
. We have already shown that Legendre symbols
can be computed in polynomial-time. Hence, the decision problem “Is
a
a square modulo
p
?” is soluble in polynomial-time. But this fact does not imply that the computational
problem “Find a square root of
a
modulo
p
” is easy.
We present two methods in this section. The Tonelli-Shanks algorithm is the best method
in practice. The Cipolla algorithm actually has better asymptotic complexity, but is usually
slower than Tonelli-Shanks.
Recall that half the integers 1
∈ N
≤
a<p
are squares modulo
p
and, if so, there are two
±
x
to the equation
x
2
≡
solutions
a
(mod
p
).
. f
(
p
)
Lemma
2.9.1
Let p
≡
3(mod4)
be prime and a
∈ N
=
1
then x
=
a
(
p
+
1)
/
4
(mod
p
)
satisfies x
2
≡
a
(mod
p
)
.
This result can be verified directly by computing
x
2
, but we give a more group-theoretic
proof that helps to motivate the general algorithm.
1)
/
2 is odd. The assumption (
p
)
Proof
Since
p
≡
3 (mod 4) it follows that
q
=
(
p
−
=
1
implies that
a
q
a
(
p
−
1)
/
2
=
≡
1(mod
p
) and so the order of
a
is odd. Therefore, a square
root of
a
is given by
a
2
−
1
(mod
q
)
x
=
(mod
p
)
.
Now, 2
−
1
(mod
q
)isjust(
q
+
1)
/
2
=
(
p
+
1)
/
4.
2
e
q
Lemma 2.9.2
Let p be a prime and suppose a is a square modulo p. Write p
−
1
=
a
(
q
+
1)
/
2
(mod
p
)
. Then w
2
where q is odd. Let w
=
≡
ab
(mod
p
)
where b has order
dividing
2
e
−
1
.
Proof
We have
w
2
a
q
+
1
aa
q
(mod
p
)
≡
≡
2
e
−
1
q
so
b
has order dividing
so
b
≡
a
q
(mod
p
). Now
a
has order dividing (
p
−
1)
/
2
=
2
e
−
1
.
The value
w
is like a “first approximation” to the square root of
a
modulo
p
. To complete
the computation it is therefore sufficient to compute a square root of
b
.
Lemma 2.9.3
Suppose
1
<n<pis such that
(
p
)
n
q
(mod
p
)
has order
=−
1
. Then y
≡
2
e
.
Proof
The order of
y
is a divisor of 2
e
. The fact
n
(
p
−
1)
/
2
≡−
1(mod
p
)impliesthat
y
satisfies
y
2
e
−
1
1(mod
p
). Hence, the order of
y
is equal to 2
e
.
≡−
