##

Pollard's
-Method

Lenstra's discovery of ECM was inspired by
Pollard's
-method, which we describe in this section.

**Definition 6.3** (Power smooth)

Let

be a positive
integer. If

is a positive integer with prime factorization

, then

is

*
-power smooth* if

for all

.

Thus
is
power smooth for
, but
is not
-power smooth (it is
-power
smooth).
We will use the following algorithm in both the Pollard
and elliptic curve factorization methods.

*Proof*.
Let

. Then

where

is the largest power of

that satisfies

.
Since

, we have

.

Let
be a positive integer that we wish to factor. We use the
Pollard
-method to look for a nontrivial factor of
as
follows. First we choose a positive integer
, usually with at most
six digits. Suppose that there is a prime divisor
of
such that
is
-power smooth. We try to find
using the following strategy. If
is an integer
not divisible by
then by Theorem 2.1.19,

Let
, and observe that our assumption that
is
-power smooth implies that
, so

Thus

If
also then
is a nontrivial factor
of
.
If
, then
for every prime power
divisor
of
. In this case, repeat the above steps but with a
smaller choice of
or possibly a different choice of
.
Also, it is a good idea to check from the
start whether or not
is not a perfect power
, and if so
replace
by
. We formalize the algorithm as follows:

For fixed
, Algorithm 6.3.3
often splits
when
is divisible
by a prime
such that
is
-power smooth.
Approximately
15% of primes
in the interval from
and
are such that
is
power-smooth, so the Pollard method with
already fails nearly 85% of the time at finding
-digit
primes in this range (see also Exercise 6.10). We
will not analyze Pollard's method further, since it was mentioned here
only to set the stage for the elliptic curve factorization method.

The following examples illustrate the Pollard
-method.

*Example 6.3*
In this example, Pollard works perfectly.
Let

. We try to use the Pollard

method with

to split

. We have

; taking

we have

and

so

is a factor of

.

*Example 6.3*
In this example, we replace

by larger integer.
Let

. With

and

we have

and

With

, we have

and

so

is a nontrivial factor of

.

*Example 6.3*
In this example, we replace

by a smaller integer.
Let

. Suppose

, so

,

and

,
so we do not obtain a factor of

.
If we replace

by

, Pollard's method works:

and

,
so we split

.

*Example 6.3*
In this example,

does not work, but

does.
Let

. Suppose

, so

,

and

,
so we do not obtain a factor of

.
If we replace

by

, then Pollard's method works:

and

. Thus

.

William
2007-06-01