Cryptography Reference
In-Depth Information
,
(
),
(
(
)),
(
(
(
))), . . .
r
f
r
f
f
r
f
f
f
r
This sequence consists of the values obtained by repeatedly applying the function
f
starting with the initial value
s
mod
p
and we expect them to be randomly and
uniformly distributed in
Z
p
is finite, the sequence must eventually repeat
a term and from this point on become cyclic. This behavior can be graphically
represented by a letter
Z
p
. Since
where the tail corresponds to the precyclic part of the
sequence and the loop to the cyclic one. Now, the interesting question is: how long
do we expect these parts to be?
It is clear from Theo
re
m 5.4 that we expect that some number in
ρ
Z
p
will be
repeated after roughly
√
p
iterations of
f
or, in other w
or
ds, that the expected length
of the tail an
d t
he loop together will be of the order of
√
p
. That is, we expect there to
be
k
(
√
p
j
f
k
=
O
)
steps with 0
≤
j
≤
k
and
f
(
r
)
=
(
r
)
. We do not know
f
because
F
j
F
k
we do not know
p
but if
u
=
(
s
)
and
v
=
(
s
)
are elements in the sequence of
j
f
k
, we have that
F
j
F
k
iterates of
F
such that
f
(
r
)
=
(
r
)
(
s
)
≡
(
s
)(
mod
p
)
or, in
other words,
u
v
but, because of the randomness
of the sequence, it is unlikely that another prime factor
q
of
n
also divides
u
≡
v
(
mod
p
)
. Then
p
divides
u
−
−
v
.
Thus we expect that
u
≡
v
(
mod
n
)
and this means that the gcd of
u
−
v
and
n
is a
proper factor of
n
and, in fact, it is probably gcd
(
u
−
v
,
n
)
=
p
.
<
√
p
Now, the problem is that w
e
cannot compute all the gcds for every pair
i
,
j
2
(
√
p
1
2
because there are about
such pairs, which would lead to a
running time estimate even worse than trial division. Fortunately, there is a wonderful
solution to this problem which is given by
Floyd's cycle-finding algorithm
.This
algorithm computes two iterates of
F
in the same loop with one instance running
twice as fast as the other one, i.e., it computes
s
i
)
=
p
/
2
=
O
(
p
)
F
i
F
2
i
=
(
s
)
and
s
2
i
=
(
s
)
together
and gcd
(
s
2
i
−
s
i
,
n
)
hoping to find
p
. Suppose then that
s
j
≡
s
k
(
mod
p
)
for some
(
√
p
j
<
k
so that, as already mentioned, we have that
k
=
O
)
.Let
l
=
k
−
j
,
so that for
i
≥
j
we have
s
i
≡
s
i
+
l
≡
s
i
+
2
l
≡
... (
mod
p
)
. Consider the value
i
=
l
j
/
l
, the first multiple of
l
that exceeds
j
. Then for this
i
we have that
