Pollard's $(p-1)$ -Method

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

Definition 6.3 (Power smooth)   Let $B$ be a positive integer. If $n$ is a positive integer with prime factorization $n=\prod p_i^{e_i}$ , then $n$ is $B$ -power smooth if $p_i^{e_i}\leq B$ for all $i$ .

Thus $30=2\cdot 3\cdot 5$ is $B$ power smooth for $B=5, 7$ , but $150=2\cdot 3 \cdot 5^2$ is not $5$ -power smooth (it is $B=25$ -power smooth).

We will use the following algorithm in both the Pollard $p-1$ and elliptic curve factorization methods.

Algorithm 6.3 (Least Common Multiple of First $B$ Integers)   Given a positive integer $B$ , this algorithm computes the least common multiple of the positive integers up to $B$ .

1. [Sieve] Using, e.g., the Sieve of Eratosthenes (Algorithm 1.2.3), compute a list $P$ of all primes $p\leq B$ .
2. [Multiply] Compute and output the product $\prod_{p\in P} p^{\lfloor \log_p(B) \rfloor}$ .

Proof. Let $m=\lcm (1,2,\ldots, B)$ . Then

$$\ord _p(m) = \max(\{\ord _p(n) : 1 \leq n \leq B\}) = \ord _p(p^r),$$

where $p^r$ is the largest power of $p$ that satisfies $p^r\leq B$ . Since $p^r\leq B < p^{r+1}$ , we have $r=\lfloor \log_p(B) \rfloor$ . $\qedsymbol$

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

$$a^{p-1}\equiv 1\pmod{p}.$$

Let $m=\lcm (1,2,3,\ldots, B)$ , and observe that our assumption that $p-1$ is $B$ -power smooth implies that $p-1\mid m$ , so

$$a^m \equiv 1 \pmod{p}.$$

Thus

$$p\mid \gcd(a^m-1,N) > 1.$$

If $\gcd(a^m-1,N)<N$ also then $\gcd(a^m-1,N)$ is a nontrivial factor of $N$ . If $\gcd(a^m-1,N)=N$ , then $a^m\equiv 1\pmod{q^r}$ for every prime power divisor $q^r$ of $N$ . In this case, repeat the above steps but with a smaller choice of $B$ or possibly a different choice of $a$ . Also, it is a good idea to check from the start whether or not $N$ is not a perfect power $M^r$ , and if so replace $N$ by $M$ . We formalize the algorithm as follows:

Algorithm 6.3 (Pollard $p-1$ Method)   Given a positive integer $N$ and a bound $B$ , this algorithm attempts to find a nontrivial factor $m$ of $N$ . (Each prime $p\mid m$ is likely to have the property that $p-1$ is $B$ -power smooth.)

1. [Compute lcm] Use Algorithm 6.3.2 to compute $m=\lcm (1,2,\ldots, B)$ .
2. [Initialize] Set $a=2$ .
3. [Power and gcd] Compute $x =a^m - 1\pmod{N}$ and $g=\gcd(x,N)$ .
4. [Finished?] If $g\neq 1$ or $N$ , output $g$ and terminate.
5. [Try Again?] If $a<10$ (say), replace $a$ by $a+1$ and go to step 3. Otherwise terminate.

For fixed $B$ , Algorithm 6.3.3 often splits $N$ when $N$ is divisible by a prime $p$ such that $p-1$ is $B$ -power smooth. Approximately 15% of primes $p$ in the interval from $10^{15}$ and $10^{15}+10000$ are such that $p-1$ is $10^6$ power-smooth, so the Pollard method with $B=10^6$ already fails nearly 85% of the time at finding $15$ -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 $(p-1)$ -method.

Example 6.3   In this example, Pollard works perfectly. Let $N=5917$ . We try to use the Pollard $p-1$ method with $B=5$ to split $N$ . We have $m = \lcm (1,2,3,4,5)=60$ ; taking $a=2$ we have

$$2^{60} - 1 \equiv 3416\pmod{5917}$$

and

$$\gcd(2^{60}-1,5917) = \gcd(3416,5917) = 61,$$

so $61$ is a factor of $5917$ .

Example 6.3   In this example, we replace $B$ by larger integer. Let $N=779167$ . With $B=5$ and $a=2$ we have

$$2^{60}-1 \equiv 710980\pmod{779167},$$

and $\gcd(2^{60}-1,779167) = 1.$ With $B=15$ , we have

$$m=\lcm (1,2,\ldots,15)=360360,$$

$$2^{360360}-1 \equiv 584876\pmod{779167},$$

and

$$\gcd(2^{360360}-1 , N) = 2003,$$

so $2003$ is a nontrivial factor of $779167$ .

Example 6.3   In this example, we replace $B$ by a smaller integer. Let $N=4331$ . Suppose $B=7$ , so $m=\lcm (1,2,\ldots,7)=420$ ,

$$2^{420} - 1 \equiv 0 \pmod{4331},$$

and $\gcd(2^{420} - 1, 4331) = 4331$ , so we do not obtain a factor of $4331$ . If we replace $B$ by $5$ , Pollard's method works:

$$2^{60} - 1\equiv 1464\pmod{4331},$$

and $\gcd(2^{60}-1,4331) = 61$ , so we split $4331$ .

Example 6.3   In this example, $a=2$ does not work, but $a=3$ does. Let $N=187$ . Suppose $B=15$ , so $m=\lcm (1,2,\ldots,15)=360360$ ,

$$2^{360360} - 1 \equiv 0 \pmod{187},$$

and $\gcd(2^{360360} - 1, 187) = 187$ , so we do not obtain a factor of $187$ . If we replace $a=2$ by $a=3$ , then Pollard's method works:

$$3^{360360} - 1\equiv 66\pmod{187},$$

and $\gcd(3^{360360}-1,187) = 11$ . Thus $187 = 11\cdot 17$ .