We will use the following algorithm in both the Pollard and elliptic curve factorization methods.
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
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.
so is a factor of .
and With , we have
so is a nontrivial factor of .
and , so we do not obtain a factor of . If we replace by , Pollard's method works:
and , so we split .
and , so we do not obtain a factor of . If we replace by , then Pollard's method works:
and . Thus .