Cryptography Reference
In-Depth Information
the running time over different choices for the pseudorandom walk. Many authors consider
the expectation of the running time over all problem instances and random choices of the
pseudorandom walk; they therefore write “expected running time” for what we are calling
“average-case expected running time”.
It is necessary to keep track of the decomposition
g
a
i
h
b
i
.
x
i
=
The values
a
i
,b
i
∈ Z
/r
Z
are obtained by setting
a
1
=
1
,b
1
=
0 and updating (for the
original rho walk)
2
a
i
(mod
r
)
if
S
(
x
i
)
=
0
a
i
+
1
=
a
i
+
u
S
(
x
i
)
(mod
r
) f
S
(
x
i
)
>
0
2
b
i
(mod
r
)
(14.4)
if
S
(
x
i
)
=
0
and
b
i
+
1
=
b
i
+
v
S
(
x
i
)
(mod
r
) f
S
(
x
i
)
>
0
.
Putting everything together, we write
(
x
i
+
1
,a
i
+
1
,b
i
+
1
)
=
walk
(
x
i
,a
i
,b
i
)
for the random walk function. But it is important to remember that
x
i
+
1
only depends on
x
i
and not on (
x
i
,a
i
,b
i
).
Exercise 14.2.2
Give the analogue of equation (
14.4
) for the additive walk.
14.2.2 Pollard rho using Floyd cycle finding
We present the original version of Pollard rho. A single sequence
x
1
,x
2
,...
of group
elements is computed. Eventually, there is a collision
x
i
=
i<j
. One pictures
the walk as having a
tail
(which is the part
x
1
,...,x
i
of the walk that is not cyclic) followed
by the
cycle
or
head
(which is the part
x
i
+
1
,...,x
j
). Drawn appropriately, this resembles
the shape of the greek letter
ρ
. The tail and cycle (or head) of such a random walk have
expected length
√
πN/
8 (see Flajolet and Odlyzko [
187
] for proofs of these, and many
other, facts).
The goal is to find integers
i
and
j
such that
x
i
=
x
j
with 1
≤
x
j
. It might seem that the only
approach is to store all the
x
i
and, for each new value
x
j
, to check if it appears in the list.
This approach would use more memory and time than the BSGS algorithm. If one were
using a truly random walk then one would have to use this approach. The whole point of
using a deterministic walk which eventually becomes cyclic is to enable better methods to
find a collision.
Let
l
t
be the length of the
tail
of the “rho” and
l
h
be the length of the
cycle
of the “rho”.
In other words, the first collision is
x
l
t
+
l
h
=
x
l
t
.
(14.5)
