Cryptography Reference
In-Depth Information
presentation brief. For further details see Section 5.6.2 of Stinson [
532
] or Section 5.2.1 of
Crandall and Pomerance [
150
].
Let
N
be a composite integer to be factored and let
p
N
be a prime (usually
p
is the
smallest prime divisor of
N
). We try to find a relation that holds modulo
p
, but not modulo
other primes dividing
N
.
The basic idea of the rho factoring algorithm is to consider the pseudorandom walk
x
1
=
|
2 and
x
i
+
1
=
f
(
x
i
)(mod
N
)
where the usual choice for
f
(
x
)is
x
2
x
2
+
1(or
f
(
x
)
=
+
a
for some small integer
a
).
Consider the values
x
i
(mod
p
) where
p
|
N
. The seque
nce
x
i
(mod
p
) is a pseudorandom
sequence of residues modulo
p
, and so after about
√
πp/
2 steps we expect there to be
indicies
i
and
j
such that
x
i
≡
x
j
(mod
p
). We call this a
collision
.If
x
i
≡
x
j
(mod
N
)
then we can split
N
as gcd(
x
i
−
x
j
,N
).
Example 14.9.1
Let
p
=
11. Then the rho iteration modulo
p
is
2
,
5
,
4
,
6
,
4
,
6
,
4
,...
Let
p
=
19. Then the sequence is
2
,
5
,
7
,
12
,
12
,
12
, ...
As with the discrete logarithm algorithms, the walk is deterministic in the sense that a
collision leads to a cycle. Let
l
t
be the length of the tail and
l
h
be the length of the cycle.
Then the first collision is
x
l
t
+
l
h
≡
x
l
t
(mod
p
)
.
We can use Floyd's cycle finding algorithm to detect the collision. The details are given in
Algorithm
20
. Note that it is not efficient to compute the gcd in line 5 of the algorithm for
each iteration; Pollard [
436
] gave a solution to reduce the number of gcd computations and
Brent [
93
] gave another.
Algorithm 20
The rho algorithm for factoring
INPUT:
N
OUTPUT: A factor of
N
1:
x
1
=
2,
x
2
=
f
(
x
1
)(mod
N
)
2:
repeat
3:
x
1
=
f
(
x
1
)(mod
N
)
x
2
=
f
(
f
(
x
2
)) (mod
N
)
4:
=
gcd(
x
2
−
d
x
1
,N
)
5:
6:
until
1
<d<N
7:
return
d
