Cryptography Reference
In-Depth Information
Algorithm 2.8. Computation of square roots modulo an odd prime
.
Input
: An odd prime
p
and an integer
a
such that
p
=
1.
Output
: A square root of
a
mod
p
.
1.
Case
p
≡
3
(
mod 4
)
:
a
mod
p
;
return
a
(
p
+
1
)/
4
mod
p
.
2.
Case
p
a
:=
:
Find a random quadratic non-residue
h
≡
1
(
mod 4
)
∈
Z
p
2
s
t
Compute
s
≥
0and
t
odd such that
p
−
1
=
A
:=
a
t
mod
p
;
H
:=
h
t
mod
p
;
v
:=
0;
for
i
from 1 to
s
−
1
do
if
(
AH
v
2
s
−
1
−
i
)
≡−
1
(
mod
p
)
then
v
:=
v
+
2
i
end if
;
end do
;
#Now
AH
v
≡
(
mod
p
)
1
, with
v
even
return
a
(
t
+
1
)/
2
H
v
/
2
mod
p
.
This algorithm is essentially due to Tonelli, who published it already in 1891. We
next prove the correctness of the algorithm and estimate its complexity:
Proposition 2.16
Algorithm 2.8 is correct and produces as output a square root of
the quadratic residue a modulo p. The expected running time of the algorithm is
O
4
(
len
(
p
)
)
.
≡
(
)
Proof
We have already shown that the algorithm is correct if
p
3
mod 4
, when
a
(
p
+
1
)/
4
mod
p
is a square root of
a
modulo
p
. So suppose that
p
in
which case we have to show that the value returned after running the
for
loop is
indeed a square root of
a
modulo
p
. It is clear that
s
≡
1
(
mod 4
)
≥
2 and
v
is initialized as
v
:=
0
so the loop is started by computing
A
2
s
−
2
mod
p
, which is a square root in
Z
p
of
A
2
s
−
1
mod
p
=
1 and hence is equal to
±
1 (in fact, the loop can also be started at
i
0 but this is unnecessary because, since
a
is a quadratic residue, we already know
that
A
2
s
−
1
mod
p
=
1). We show by induction on
i
that, after running the
i
th iteration
of the loop which includes updating the value of
v
,
=
2
s
−
1
−
i
AH
v
,
i.e., the value 1 is maintained for this expression after each iteration of the loop.
We may s t ar t a t
i
(
)
≡
1
(
mod
p
)
0, after which we have the value 1 as already remarked. So
suppose that we also have the value 1 after the
=
(
i
−
1
)
th iteration of the loop, i.e.,
2
s
−
i
2
s
−
i
−
1
AH
v
AH
v
(
mod
p
which is a square root of the previous value 1 (as
v
has not been updated yet) and
hence it is equal to
)
≡
1
(
mod
p
)
. Then in the
i
th iteration we compute
(
)
±
1. If the value is 1 then we have nothing to prove, so assume
2
s
−
i
−
1
AH
v
that
(
)
≡−
1
(
mod
p
)
. In this case the value of
v
is updated in the loop
AH
v
+
2
i
2
s
−
i
−
1
2
i
to
v
:=
v
+
and so we have to show that
(
)
≡
1
(
mod
p
)
.This
AH
v
+
2
i
2
s
−
i
−
1
2
s
−
i
−
1
H
2
i
2
s
−
1
−
i
H
2
s
−
1
AH
v
is indeed true because
(
)
≡
(
)
(
)
≡
(
−
1
)
≡
