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.

Algorithm 6.3 (Least Common Multiple of First Integers)   Given a positive integer , this algorithm computes the least common multiple of the positive integers up to .
1. [Sieve] Using, e.g., the Sieve of Eratosthenes (Algorithm 1.2.3), compute a list  of all primes .
2. [Multiply] Compute and output the product .

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:

Algorithm 6.3 (Pollard Method)   Given a positive integer and a bound , this algorithm attempts to find a nontrivial factor of . (Each prime is likely to have the property that is -power smooth.)
1. [Compute lcm] Use Algorithm 6.3.2 to compute .
2. [Initialize] Set .
3. [Power and gcd] Compute and .
4. [Finished?] If or , output and terminate.
5. [Try Again?] If (say), replace by and go to step 3. Otherwise terminate.

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