Cryptography Reference
In-Depth Information
(71
,
69)
,
(
u
3
,v
3
)
=
(76
,
18) so that
g
1
=
343
,g
2
=
676
,g
3
=
627. One computes the table
of values (
x
i
,a
i
,b
i
) as follows:
i
i
a
i
b
i
S
(
x
i
)
1 9101
2
594
38
34
2
3
280
8
2
0
4
736
16
4
0
5
475
32
8
3
6
113
7
26
1
7
736
44
60
0
It follows that
l
t
=
4 and
l
h
=
3 and so the first collision detected by Floyd's method is
x
6
=
x
12
. We leave as an exercise to verify that the discrete logarithm in this case is 50.
Exercise 14.2.7
Let
p
5 which can be checked to have
order 71 modulo
p
. Use the rho algorithm to compute the discrete logarithm of
h
to the
base
g
modulo
p
.
=
569 and let
g
=
262 and
h
=
Exercise 14.2.8
One can simplify Definition
14.2.1
and equation (
14.4
) by replacing
g
j
by
either
g
u
j
or
h
v
j
(independently for each
j
). Show that this saves one modular addition in
each iteration of the algorithm. Explain why this optimisation should not affect the success
of the algorithm as long as the walk uses all values for
S
(
x
i
) with roughly equal probability.
Algorithm
15
always terminates, but there are several things that can go wrong:
b
2
) may not be invertible modulo
r
.
Hence, we can only expect to prove that the algorithm succeeds with a certain proba-
bility (extremely close to 1).
The cycle may be very long (as big as
r
) in which case the algorithm is slower than brute
force search.
Hence, we can only expect to prove an expected running time for the algorithm. We
recall that the expected running time in this case is the average, over all choices for the
function
walk
, of the worst-case running time of the algorithm over all problem instances.
The value (
b
1
−
Note that the algorithm always halts, but it may fail to output a solution to the DLP.
Hence, this is a Monte Carlo algorithm.
14.2.3 Other cycle finding methods
Floyd cycle finding is not a very efficient way to find cycles. Though any cycle finding
method requires computing at least
l
t
+
l
h
group operations, Floyd's method needs on
average 2
.
47(
l
t
+
l
h
) group operations (2
.
47 is 3 times the expected value of the epact).
