Cryptography Reference
In-Depth Information
Z
p
is a cyclic group, it follows that
y
generates the full subgroup of elements
of order dividing 2
e
. Hence,
b
Since
y
i
(mod
p
)forsome1
2
e
. Furthermore, since the
=
≤
i
≤
order of
b
divides 2
e
−
1
, it follows that
i
is even.
Writing
i
w/y
j
(mod
p
) then
=
2
j
and
x
=
x
2
w
2
/y
2
j
≡
≡
ab/b
≡
a
(mod
p
)
.
Hence, if one can compute
i
then one can compute the square root of
a
.
If
e
is small then the value
i
can be found by a brute-force search. A more advanced
method is to use the Pohlig-Hellman method to solve the discrete logarithm of
b
to the base
y
(see Section
13.2
for an explanation of these terms). This idea leads to the Tonelli-Shanks
algorithm for computing square roots modulo
p
(see Section 1.3.3 of [
60
] or Section 1.5
of [
127
]).
Algorithm 3
Tonelli-Shanks algorithm
INPUT:
a
,
p
such that (
p
)
=
1
OUTPUT:
x
such that
x
2
≡
a
(mod
p
)
2
e
q
where
q
is odd
2:
Choose random integers 1
<n<p
until (
p
)
1:
Write
p
−
1
=
=−
1
n
q
(mod
p
)
3:
Set
y
=
a
(
q
+
1)
/
2
a
q
(mod
p
)
4:
Set
w
=
(mod
p
) and
b
=
y
2
j
(mod
p
)
5:
Compute an integer
j
such that
b
≡
6:
return
w/y
j
(mod
p
)
Exercise 2.9.4
Compute
√
3 modulo 61 using the Tonelli-Shanks algorithm.
Line 2 of Algorithm
3
is randomised, but the rest of the algorithm is deterministic. The
complexity is dominated by the cost of computing exponentiations such as
n
q
(mod
p
)in
lines 3 and 4 (which take
O
(log(
q
)
M
(log(
p
))) bit operations), and the cost of computing
j
in line 5. When
e
is large the latter cost dominates. A complexity of
O
(log(
p
)
2
M
(log(
p
)))
bit operations for the Pohlig-Hellman method is determined in Exercise
13.2.6
(and an
improved complexity is given in equation (
13.1
)). In practice, when
e
is large, one uses the
Cipolla method (see Exercise
2.9.7
below, Section 7.2 of [
21
] or Section 3.5 of [
376
]). The
Cipolla method is expected to perform
O
(log(
p
)
M
(log(
p
))) bit operations. This complexity
can also be obtained using general-purpose polynomial factorisation (see Exercise
2.12.6
).
Exercise 2.9.5
Let
r
∈ N
. Generalise the Tonelli-Shanks algorithm so that it computes
r
th
roots in
F
p
(the only non-trivial case being when
p
≡
1(mod
r
)).
such that (
p
)
Exercise 2.9.6
(Atkin) Let
p
≡
5(mod8) be prime and
a
∈ Z
=
1. Let
(2
a
)
(
p
−
5)
/
8
2
az
2
(mod
p
). Show that
i
2
z
=
(mod
p
) and
i
=
=−
1(mod
p
) and that
w
=
1) satisfies
w
2
az
(
i
−
≡
a
(mod
p
).