Cryptography Reference
In-Depth Information
Exercise 15.5.5
Write the above algorithm in pseudocode (using trial division to determine
the smooth relations).
Exercise 15.5.6
Let the notation be as above. Let
T
B
be the expected number of trials of
random integers modulo
p
until one is
B
-smooth. Show that the expected running time
of this algorithm (using naive trial division for the relations and using the Lanczos or
Wiedemann methods for the linear algebra) is
)
2
T
B
M
(log(
p
))
)
2
+
o
(1)
M
(log(
r
)))
O
((#
B
+
(#
B
bit operations as
p
→∞
Exercise 15.5.7
Show that taking
B
L
p
(1
/
2
,
1
/
2) is the optimal value to minimise
the complexity of the above algorithm, giving a complexity of
O
(
L
p
(1
/
2
,
2
=
+
o
(1))) bit
F
p
as
p
operations for the discrete logarithm problem in
. (Note that, unlike many of
the results in this chapter, this result does not rely on any heuristics.)
→∞
We remark that, in practice, rather than computing a full exponentiation
g
z
one might
use a pseudorandom walk as done in Pollard rho. For further implementation tricks see
Sections 5.1 to 5.5 of Odlyzko [
421
].
If
g
does not have prime order (e.g., suppose
g
is a generator of
F
p
and has order
p
1)
then there are several options: one can apply Pohlig-Hellman and reduce to subgroups of
prime order and apply index calculus in each subgroup (or at least the ones of large order).
Alternatively, one can apply the algorithm as above and perform the linear algebra modulo
the order of
g
. There will usually be difficulties with non-invertible elements in the linear
algebra, and there are several solutions, such as computing the Hermite normal form of
the relation matrix or using the Chinese remainder theorem, we refer to Section 5.5.2 of
Cohen [
127
] and Section 15.2.1 of Joux [
283
] for details.
−
Exercise 15.5.8
Give an algorithm similar to the above that works when
r
2
|
(
p
−
1).
Exercise 15.5.9
This exercise is about solving many different discrete logarithm instances
h
i
=
g
a
i
(mod
p
), for 1
n
, to the same base
g
. Once sufficiently many relations are
found, determine the cost of solving each individual instance of the DLP. Hence, show
that one can solve any constant number of instances of the DLP to a given base
g
≤
i
≤
∈ F
p
in
O
(
L
p
(1
/
2
,
2
+
o
(1))) bit operations as
p
→∞
.
15.5.2 Heuristic algorithms for discrete logarithms modulo
p
To get a faster algorithm it is necessary to improve the time to find smooth relations. It
is natural to seek methods to sieve rather than factor each value by trial division, but it is
not known how to do this for relations of the form in equation (
15.7
). It would also be
natural to find an analogue to Pomerance's method of considering residues of size about
the square-root of random; Exercise
15.5.10
gives an approach to this, but it does not lower
the complexity.
