Cryptography Reference
In-Depth Information
We take a random
x
0
, and iterate
x
i
+
1
=
f
(
x
i
) mod
n
. Due to the property
of the
f
function, this modulo
n
computation actually “hides” the modulo
p
computation: if we define
x
i
+
1
=
f
(
x
i
) mod
p
with
x
0
=
x
0
, we obtain that
x
i
=
0.
Since
Z
p
is a finite set, we expect that the
x
i
sequence will at one point enter
into a loop. The shape of the sequence will then look like the Greek character
Rho (
x
i
mod
p
for any
i
>
): with a tail and a loop. If
f
is random, there is no reason for this loop
modulo
p
to correspond to a loop modulo
n
: for instance, unless
n
is not a
power of
p
, there exists another prime factor
q
, and we know from the Chinese
Remainder Theorem that the modulo
p
and modulo
q
computations are totally
independent. So a loop modulo
p
will rarely synchronize with a loop modulo
q
.
This loop is easy to detect by gcd computations. Furthermore, random mappings
analysis shows t
ha
t we can expect the total length of the Rho (the tail and the
loop) to be
ρ
(
√
p
). This is similar to the
birthday paradox
effect.
O
In order to detect a loop, we can just iterate the following process:
1:
a
←
x
0
,
b
←
x
0
2:
while
a
=
b
do
a
←
f
(
a
)
3:
f
(
f
(
b
))
5:
end while
b
←
4:
The
a
register contains
x
t
and the
b
register contains
x
2
t
in the
t
-th iteration where
x
0
,
x
1
,...
is the sequence obtained by iterating
f
on
x
0
. Eventually we will find
x
t
=
x
2
t
when
t
is greater than the tail length and a multiple of the loop length.
In order to do the same with a “hidden computation” in
Z
p
, we notice that we only
have to check equalities. If computations are performed in
Z
n
, we can check hidden
equalities in
Z
p
between
a
and
b
by computing the gcd of
a
b
and
n
. In case of
equality, the gcd will be a multiple of
p
. Hence the algorithm in Fig. 7.5 eventually
stops after a number of iterations which is a big
−
O
of the rho length.
Input
:
n
, an integer with a prime factor smaller than
B
Output
: a nontrivi
al
factor of
n
Complexity
:
(
√
B
) arithmetic operations
O
1:
x
0
←
random,
a
←
x
0
,
b
←
x
0
2:
repeat
3:
a
←
f
(
a
) mod
n
f
(
f
(
b
) mod
n
) mod
n
5:
until
gcd(
a
b
←
4:
−
b
,
n
)
=
1
6:
output the gcd
Figure 7.5.
Pollard Rho Factorization Algorithm.
Search WWH ::
Custom Search