Cryptography Reference
In-Depth Information
The first key argument is now to realize that equalities in
Z
p
are independent from
equalities in
Z
n
, which means that the case of full equality in
Z
n
is negligible. This
means that the gcd will be a nontrivial factor of
n
which contains
p
.
The second key argument is the comple
x
ity analysis: we can prove that if
x
0
and
f
are random, then
t
he rho length is
(
√
p
). Hence the algorithm works within a
O
(
√
p
) arithmetic operations where
p
is the smallest factor of
n
.In
Fig. 7.5 the complexity in
t
erms of an upper bound
B
on
p
is given. F
or
all composite
numbers, we have
B
complexity of
O
≤
√
n
so we factorize a general integer
n
in
(
4
√
n
).
O
We use the following result for the complexity analysis.
Lemma 7.8.
Let f be a random function in a set of p elements
, and
let x
0
be a random
element. We iteratively define x
t
+
1
=
+
√
2
f
(
x
t
)
and let t
=
1
λ
p
for a given real
λ
.
x
t
are pairwise different is less than e
−
λ
.
The probability that x
0
,x
1
,...,
Proof.
Since
f
is random, this probability is
1
t
i
p
p
=
−
.
i
=
1
≥
√
2
t
(
t
+
1)
Since log(1
−
x
)
<
−
x
for 0
<
x
<
1, log
p
is lesser than
−
. Since
t
λ
p
,
2
p
this is smaller than
−
λ
.
x
2
1 and
x
0
=
2347. The iterations yield the data given in Fig. 7.6 and ends by pulling out the factor
127. Then we can see that, indeed, 18923
As an example, we try to factorize
n
=
18923. We let
f
(
x
)
=
+
=
127
×
149.
7.2.2
Pollard
p
−
1
Method
The Pollard Rho algorithm works well for numbers
n
featuring a relatively small factor.
We can find another method when
n
has a prime factor
p
such that all prime factors of
t
=
1
a
=
1817
b
=
8888
gcd
=
1
t
=
2
a
=
8888
b
=
12599
gcd
=
1
=
=
=
=
t
3
a
11943
b
13068
gcd
1
t
=
4
a
=
12599
b
=
1342
gcd
=
1
t
=
5
a
=
8678
b
=
10137
gcd
=
1
t
=
6
a
=
13068
b
=
7978
gcd
=
1
=
=
=
=
t
7
a
11473
b
8232
gcd
1
t
=
8
a
=
1342
b
=
16487
gcd
=
1
t
=
9
a
=
3280
b
=
11407
gcd
=
1
t
=
10
a
=
10137
b
=
11280
gcd
=
127
Figure 7.6.
Example of Pollard Rho factorization.
Search WWH ::
Custom Search