Cryptography Reference
In-Depth Information
Floyd's cycle finding
algorithm
3
is to compare
x
i
and
x
2
i
. Lemma
14.2.3
shows that this
will find a collision in at most
l
t
+
l
h
steps. The crucial advantage of comparing
x
2
i
and
x
i
is that it only requires storing two group elements. The rho algorithm with Floyd cycle
finding is given in Algorithm
15
.
Algorithm 15
The rho algorithm
INPUT:
g,h
G
OUTPUT:
a
such that
h
∈
g
a
,or
⊥
1:
Choose randomly the function
walk
as explained above
2:
x
1
=
=
g,a
1
=
1
,b
1
=
0
3:
(
x
2
,a
2
,b
2
)
=
walk
(
x
1
,a
1
,b
1
)
4:
while
(
x
1
=
x
2
)
do
=
(
x
1
,a
1
,b
1
)
walk
(
x
1
,a
1
,b
1
)
5:
(
x
2
,a
2
,b
2
)
=
walk
(
walk
(
x
2
,a
2
,b
2
))
6:
7:
end while
8:
if
b
1
≡
b
2
(mod
r
)
then
return
⊥
9:
10:
else
11:
b
2
)
−
1
return
(
a
2
−
a
1
)(
b
1
−
(mod
r
)
12:
end if
Lemma 14.2.3
Let the notation be as above. Then x
2
i
=
x
i
if and only if l
h
|
i and i
≥
l
t
.
Further, there is some l
t
≤
i<l
t
+
l
h
such that x
2
i
=
x
i
.
Proof
If
x
i
=
j
). Hence, the first statement of the Lemma
is clear. The second statement follows since there is some multiple of
l
h
between
l
t
and
l
t
+
x
j
then we must have
l
h
|
(
i
−
l
h
.
∈ F
p
.Let
n
S
=
Exercise 14.2.4
Let
p
=
347,
r
=
173,
g
=
3
,h
=
11
3. Determine
l
t
and
l
h
for the values (
u
1
,v
1
)
=
(1
,
1), (
u
2
,v
2
)
=
(13
,
17). What is the smallest of
i
for which
x
2
i
=
x
i
?
Exercise 14.2.5
Repeat Exercise
14.2.4
for
g
=
11,
h
=
3(
u
1
,v
1
)
=
(4
,
7) and (
u
2
,v
2
)
=
(23
,
5).
The smallest index
i
such that
x
2
i
=
x
i
is cal
led th
e
epact
. The expected value of the
epact is conjectured to be approximately 0
.
823
√
πr/
2.
F
p
.Let
Example 14.2.6
Let
p
=
809 and consider
g
=
89 which has prime order 101 in
h
=
799 which lies in the subgroup generated by
g
.
Let
n
S
=
g<
809, represent this integer in its
usual binary expansion and then reduce modulo 4. Choose (
u
1
,v
1
)
4. To define
S
(
g
) write
g
in the range 1
≤
=
(37
,
34)
,
(
u
2
,v
2
)
=
3
Apparently this algorithm first appears in print in Knuth [
308
], but is credited there to Floyd.
