Cryptography Reference
In-Depth Information
7.3.1.2
P
±
1
In the 1970s, John M. Pollard developed and proposed two special-purpose integer
factorization algorithms that are optimized to find small prime factors. The first
algorithm is known as P
1.
Let
n
be the integer to be factorized and
p
be some (yet unknown) prime factor
of
n
,forwhich
p
−
1 is the product of possibly many
prime numbers that are smaller than or equal to
B
(see Definition 3.28). If
k
is the
product of all prime numbers that are smaller than or equal to
B
,then
k
is a multiple
of
p
−
1 is
B
-smooth—that is,
p
−
1. Now consider what happens if we take a small integer (e.g.
a
=2)andset
it to the power of
k
. Fermat's Little Theorem (i.e., Theorem 3.7) tells us that
−
a
k
≡
1(mod
p
)
,
and hence
p
divides
a
k
1. On the other hand,
p
must also divide
n
(remember that
p
is supposed to be a prime factor of
n
), and hence
p
divides the greatest common
divisor of
a
k
−
−
1 and
n
(i.e.,
p
|
gcd
(
a
k
−
1
,n
)). Note that
k
might be very large,
but
a
k
1 can always be reduced modulo
n
.
Note that one knows neither the prime factorization of
p
−
1 nor the bound
before one starts the algorithm. So one has to begin with an initially chosen bound
B
and perhaps increase it during the execution of the algorithm. Consequently, the
algorithm is practical only if
B
is not too large. For the typical size of prime numbers
in use today (e.g., for the RSA public key cryptosystem), the probability that one can
factorize
n
using Pollard's P
−
1 algorithm is pretty small. Nevertheless, the mere
existence of the algorithm is a reason that some cryptographic standards require
RSA moduli to have prime factors
p
for which
p
−
1 has at least one large prime
factor. In the literature, such primes are frequently called
strong
.
In either case, the running time of Pollard's P
−
−
1 algorithm is
O
(
|
t
|
),where
t
is the largest prime power dividing
p
−
1. Pollard's P
−
1 algorithm was later modified
and a corresponding P+1 algorithm was proposed.
7.3.1.3
Pollard Rho
The second algorithm developed and proposed by Pollard in the 1970s is known
as
Pollard Rho
. The basic idea is to have the algorithm successively draw random
numbers less than
n
.If
p
is a (yet unknown) prime factor of
n
, then it follows from
the birthday paradox (see Section 8.1) that after about
p
1
/
2
=
√
p
rounds one has
drawn
x
i
and
x
j
with
x
i
x
j
(mod
p
). If this occurs, one knows that
p
divides the greatest common divisor of
x
i
−
=
x
j
and
x
i
≡
x
j
and
n
(i.e.,
p
|
gcd
(
x
i
−
x
j
,n
)).
