Cryptography Reference
In-Depth Information
The Pollard Rho algorithm has a running time of
O
(
√
p
)
where
p
is the smallest prime factor of
n
,or
O
(
√
n
)=
O
(
n
1
/
4
)=
O
(
e
ln(
n
1
/
4
)
)
in the worst case. Consequently, the Pollard Rho algorithm is an algorithm that is
exponential in ln
n
, and as such it can only be used if
p
is small compared to
n
.For
the size of the integers that are used today, the algorithm is still impractical. It was,
however, used on the factorization of the eighth Fermat number
F
8
=2
2
8
+1=2
256
+1
,
which unexpectedly turned out to have a small prime factor. In either case, the space
requirements of the Pollard Rho algorithm are small.
7.3.1.4
ECM
In the 1980s, Hendrik W. Lenstra developed and proposed the ECM [4]. It can
be best thought of as a generalization or randomized version of Pollard's P
−
1
algorithm. The success of Pollard's P
−
1 algorithm depends on
n
having a divisor
p
such that
p
1 is smooth. If no such
p
exists, then the algorithm fails. The ECM
randomizes the choice, replacing the group
−
Z
p
used in Pollard's P
−
1 algorithm by
a random (or pseudorandom) elliptic curve over
GF
(
p
).
The ECM has a subexponential running time. Its average-case (worst-case)
running time is
L
p
[
2
,
√
2] (
L
n
[
2
,
1]). The worst case occurs when
p
is roughly
√
n
,
which is often the case when one uses RSA or some other public key cryptosystem.
So, although the ECM cannot be considered a threat against the standard RSA public
key cryptosystem that uses two primes, it must nevertheless be taken into account
when one implements the so-called multiprime RSA system, where the modulus
may have more than two prime factors.
7.3.2
General-Purpose Algorithms
Examples of general-purpose integer factorization include continued fraction, the
quadratic sieve (QS), and the number field sieve (NFS).
