Cryptography Reference
In-Depth Information
We now briefly discuss the complexity of the algorithm. Note that the “algorithm” may
not terminate, for example if the length of the cycle and tail are the same for all
p
N
then the gcd will always be either 1 or
N
. In practice, one would stop the algorithm after
a certain number of steps and repeat with a different choice of
x
1
and/or
f
(
x
). Even if it
terminates, the length of the cycle of the rho may be very large. Hence, the usual approach
is to make the heuristic assumption that the rho pseudorandom walk behaves like a random
walk. To have meaningful heuristics one should analyse the algorithm when the function
f
(
x
) is randomly chosen from a large set of possible functions.
Note that the rho method is more general t
ha
n the
p
|
−
1 method (see Section
12.3
),
N
is not very likely to be
√
p
-smooth.
|
since a random
p
Theorem 14.9.2
Let N be composite, not a prime power and not too smooth. Assume that
the Pollard rho walk modulo p behaves like a pseudorandom walk for all p
|
N. Then the
rho algorithm factors N in O
(
N
1
/
4
log(
N
)
2
)
bit operations.
√
N
. Define the values
l
t
and
l
h
corresponding to the sequence
x
i
(mod
p
). If the walk be
haves
sufficiently like a random
≤
Proof
(Sketch) Let
p
be a prime dividing
N
such that
p
walk then, by the birthday paradox, we will have
l
h
,l
t
≈
√
πp/
8. Similarly, for some other
prim
e
q
N
one expects that the walk modulo
q
has different values
l
h
and
l
t
. Hence, after
O
(
√
p
) iterations of the loop one expects to split
N
.
|
Bach [
20
] has given a rigorous analysis of the rho factoring algorithm. He proves
that if 0
x
i
+
y
,
then the probability of finding the smallest prime factor
p
of
N
after
k
steps is at least
k
(
k
≤
x,y <N
are chosen randomly and the iteration is
x
1
=
x
,
x
i
+
1
=
O
(
p
−
3
/
2
)as
p
goes to infinity, where the constant in the
O
depends on
k
.
Bach's method cannot be used to analyse the rho algorithm for discrete logarithms.
−
1)
/
2
p
+
Example 14.9.3
Let
N
=
144493. The values (
x
i
,x
2
i
)for
i
=
1
,
2
,...,
7are
(2
,
5)
,
(5
,
677)
,
(26
,
9120)
,
(677
,
81496)
,
(24851
,
144003)
,
(9120
,
117992)
,
(90926
,
94594)
and one can check that gcd(
x
14
−
131.
The reason for this can be seen by considering the values
x
i
modulo
p
x
7
,N
)
=
=
131. The
sequence of values starts
2
,
5
,
26
,
22
,
92
,
81
,
12
,
14
,
66
,
34
,
109
,
92
and we see that
x
12
=
x
5
=
92. The tail has length
l
t
=
5 and the head has length
l
h
=
7.
Clearly,
x
14
≡
x
7
(mod
p
).
Exercise 14.9.4
Factor the number 576229 using the rho algorithm.
x
2
Exercise 14.9.5
The rho algorithm usually uses the function
f
(
x
)
=
+
1. Why do you
x
2
x
2
think this function is used? Why are the functions
f
(
x
)
=
and
f
(
x
)
=
−
2less
suitable?
