Cryptography Reference
In-Depth Information
(where we used the fact that
H
2
s
−
1
(
−
,
as we have seen in our previous discussion). After the last iteration of the loop,
corresponding to
i
1
)(
−
1
)
≡
1
(
mod
p
)
≡−
1
(
mod
p
)
1, we have that
AH
v
and hence the final
value of
v
is the integer 2
u
in our previous discussion and
a
(
t
+
1
)/
2
H
v
/
2
mod
p
is
indeed a square root of
a
modulo
p
.
For the complexity of the algorithm observe that, given a non-square
h
, outside the
for
loop only a few exponentiations modulo
p
are computed in time
O
=
s
−
≡
1
(
mod
p
)
3
(
len
(
p
)
)
.
The loop has
s
iterations in which, again, modular exponentiations
are carried out, so the complexity is
O
−
1
=
O
(
len
(
p
))
3
4
(
(
)
(
)
)
=
(
(
)
)
. Finally, as
we have remarked, the expected number of trials to find a non-residue is 2 and each
trial uses Algorithm 2.7 which has complexity
O
len
p
len
p
O
len
p
2
(
len
(
p
)
)
so the expected running
2
time of this part of the algorithm is
O
(
len
(
p
)
)
. Thus the expected running time of
4
Algorithm 2.8 is
O
(
len
(
p
)
)
.
Remark 2.12
Observe that in the estimation of the complexity of Algorithm 2.8 we
used the fact that
s
this
bound is not very tight and, by considering average instead of worst-case complex-
ity, one obtains the estimate
O
=
O
(
len
(
p
))
. Since
s
is usually much smaller than len
(
p
)
3
(
len
(
p
)
)
, which better reflects the behavior of the
algorithm over many random primes.
Exercise 2.45
Prove that the case
p
≡
3
(
mod 4
)
of Algorithm 2.8 is also handled
by the algorithm used when
p
, so that it was not strictly necessary to
include it as a separate case. To see this, show that if
p
≡
1
(
mod 4
)
≡
3
(
mod 4
)
then
s
=
1 and
hence
A
has order 1, that is
A
≡
1
(
mod
p
)
. Thus
v
=
0 and the root is obtained as
a
(
t
+
1
)/
2
a
(
p
+
1
)/
4
≡
(
).
mod
p
Remark 2.13
When
p
2
instead of a random non-square. Then we can prove that the algorithm computes a
square root
x
of
a
as follows: set
x
≡
5
(
mod 8
)
, Algorithm 2.8 can be modified to use
h
=
a
(
p
+
3
)/
8
mod
p
and if
x
2
:=
≡
a
(
mod
p
)
then
x
2
(
p
−
1
)/
4
mod
p
. Indeed, it is easy to see that in this case we have
s
x
:=
=
2 and
t
4 and, since 2 is a quadratic non-residue modulo
p
by Theorem 2.24,
we may choose
h
=
(
p
−
1
)/
=
2. Then, when entering the
for
loop with
v
=
0 and
i
=
1we
a
t
a
(
p
−
1
)/
4
mod
p
. This can only take the values 1 or
have to compute
A
=
=
−
1.
a
(
p
+
3
)/
8
2
a
(
p
+
3
)/
4
a
(
p
−
1
)/
4
The first case occurs when
,
so that
a
(
p
+
3
)/
8
mod
p
is indeed a square root in this case. The second case makes
v
(
)
≡
≡
a
·
≡
a
(
mod
p
)
a
(
t
+
1
)/
2
2
(
p
−
1
)/
4
a
(
p
+
3
)/
8
2
(
p
−
1
)/
4
:=
2 and returns the root
x
≡
≡
(
mod
p
).
Example 2.31
The algorithm for computing square roots modulo primes is used in
several cryptologic algorithms and, in particular, in the quadratic sieve and number
how the Fermat number
F
7
=
2
2
7
1 is factored with the quadratic sieve, for which
purpose the square roots of
F
7
modulo
p
are computed for a set of primes modulo
which
F
7
is a quadratic residue. One of these primes is:
+
> p:= 31873:
