Pollard's p-1 | Mathematical Cryptography

Pollard’s p-1 factorization algorithm was invented by John Pollard in 1974. This factoring algorithm is based on Fermat Little Theorem. This algorithm is promising for factoring the composite number $n$ with a prime divisor $p$ such that $p-1$ has small prime factors. As a result, for any cryptosystem whose security is based on the hardness of the problem of factoring (e.g., RSA), it is critical that $p-1$ has at least one large prime factor.

The Ideas of Pollard’s p-1 Method

Let $p$ is a prime. According to Fermat Little Theorem, $a^{p-1} \equiv 1$ modulo $p$ whenever $a$ is an integer relatively prime to $p$ . Furthermore, if $a^M \equiv 1$ modulo $p$ , then $p-1$ divides $M$ . These two facts form the basis for Pollard’s p-1 method.

Let $N=p \times q$ where $p$ and $q$ are two distinct prime numbers. First, we describe the overall strategy of Pollard’s p-1 factorization algorithm. The goal is to find a number $M$ such that $p-1$ divides $M$ but $q-1$ does not divide $M$ . Suppose such a number $M$ is found. Then for some random number $a$ , we have $a^M \equiv 1 \ \text{mod} \ p$ since Fermat Little Theorem tells us that $a^{p-1} \equiv 1 \ \text{mod} \ p$ . On the other hand, $a^M \not \equiv 1 \ \text{mod} \ q$ . Otherwise, we would have $q-1$ divides $M$ . The fact $a^M \not \equiv 1 \ \text{mod} \ q$ implies that $a^M \not \equiv 1 \ \text{mod} \ N$ .

With $a^M \equiv 1 \ \text{mod} \ p$ , we know that the prime $p$ divides $a^M-1$ . We also know that $p$ divides $N$ . Furthermore, we know that $N$ does not divide $a^M-1$ . Thus $p$ is the greatest common divisor of $a^M-1$ and $N$ , denoted by $p=\text{GCD}(a^M-1,N)$ . Assuming that we can find $M$ , taking the GCD of $a^M-1$ and $N$ would yield the prime factor $p$ of $N$ .

The idea sounds wonderful. How do we find such a number $M$ . Note that The number $M$ captures $p-1$ in that $p-1$ divides $M$ or $M=(p-1) \times k$ for some number $k$ . We can find $M$ iteratively. Choose a random number $a$ with $1 < a < n$ . Start with $n!$ for a relatively small $n$ . Compute $a^{n!} \ \text{mod} \ N$ . Compute the GCD of the numbers $a^{n!}-1$ and $N$ , denoted by $\text{GCD}(a^{n!}-1,N)$ . If $\text{GCD}(a^{n!}-1,N)>1$ , then the GCD is a prime factor of $N$ . If the GCD is 1, then we compute $a^{(n+1)!} \ \text{mod} \ N$ and then compute $\text{GCD}(a^{(n+1)!}-1,N)$ and so on. One possibility o speeding up the calculation is that instead of incrementing the factorial by 1, we can increase it by a pre-determined value $k$ . That is, instead of using $(n+1)!$ , we can use $(n+k)!$ in the next step.

Some comments about the calculation. We do not have to derive the exact values of $n!$ except for the first one. To start, we can compute the exact value of $n!$ to compute $a^{n!} \ \text{mod} \ N$ . If we need to evaluate $a^{(n+1)!}$ , we simply perform the exponentiation $(a^{n!})^{n+1} \ \text{mod} \ N$ . Furthermore, the exponentiation $a^{n!}$ does not have to be the exact value. It can be evaluated modulo $N$ . We can choose a random number $a$ to work as the base. In practice, we can use 2. Examples are given in the next section to illustrate the algorithm.

Examples

Example 1
Use Pollard’s p-1 method to factor the integer $N$ = 1,048,561. This is a semiprime, meaning that it is a product of two prime factors.

We use $10!$ to start. We have $10!$ = 3,628,800 and $\text{GCD}(2^{10!}-1,N)=1$ . Then we continue the calculation with larger factorials. We have the following results.

$\displaystyle 2^{10!} \equiv 225138 \ \text{mod} \ N$ …………… $\text{GCD}(2^{10!}-1,N)=1$
$\displaystyle 2^{11!} \equiv 660641 \ \text{mod} \ N$ …………… $\text{GCD}(2^{11!}-1,N)=1$
$\displaystyle 2^{12!} \equiv 1024940 \ \text{mod} \ N$ ………….. $\text{GCD}(2^{12!}-1,N)=1$
$\displaystyle 2^{13!} \equiv 69237 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{13!}-1,N)=911$

Thus, 911 is one of the prime factors of $N$ = 1,048,561. Then the prime factorization is $N$ = 911 x 1151. To see why we only need to go up to $13!$ in the calculation, with $p$ = 911 and $q$ = 1151, we have $p-1$ = 2 x 5 x 7 x 13 and $q-1$ = 2 x 25 x 23. The largest prime factor of $p-1$ is 13 and the largest prime factor of $q-1$ is 23. Furthermore, $p-1$ divides $13!$ and $q-1$ does not divide $13!$ . Thus, $13!$ is the desired $M$ described above. $\square$

Example 2
Use Pollard’s p-1 algorithm to factor the number $N$ = 120,035,047,163, which is a product of two prime numbers.

We use the starting point $11!$ = 39,916,800. With the GCDs being 1 for quite a few higher factorials, we only show the calculation leading to the last step.

$\displaystyle 2^{11!} \equiv 104220222835 \ \text{mod} \ N$ …………… $\text{GCD}(2^{11!}-1,N)=1$

$\displaystyle 2^{30!} \equiv 115085159489 \ \text{mod} \ N$ …………… $\text{GCD}(2^{30!}-1,N)=1$
$\displaystyle 2^{31!} \equiv 70238389359 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{31!}-1,N)=1$
$\displaystyle 2^{32!} \equiv 26731042480 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{32!}-1,N)=1$
$\displaystyle 2^{33!} \equiv 50408736108 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{33!}-1,N)=1$
$\displaystyle 2^{34!} \equiv 117848667792 \ \text{mod} \ N$ …………… $\text{GCD}(2^{34!}-1,N)=1$
$\displaystyle 2^{35!} \equiv 71394351228 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{35!}-1,N)=1$
$\displaystyle 2^{36!} \equiv 87224960905 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{36!}-1,N)=1$
$\displaystyle 2^{37!} \equiv 1891194340 \ \text{mod} \ N$ ………………. $\text{GCD}(2^{37!}-1,N)=1$
$\displaystyle 2^{38!} \equiv 94274356142 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{38!}-1,N)=1299601$

Thus, the factorization of $N$ is 1,299,601 x 92,363. With $p$ = 1,299,601 and $q$ = 92,363, let’s look at the factors of $p-1$ and $q-1$ .

$p-1=2^4 \times 3^2 \times 5^2 \times 19^2$

$q-1=2 \times 46181$

Now we know that $p-1$ is made up of small primes with the largest being 19 while $q-1$ has a large prime factor (relatively speaking). Note that $p-1$ does not divide $19!$ since 19 has exponent 2 in the factorization of $p-1$ . This lengthens the calculation to $38!$ . Thus, with $M=38!$ , we know that $p-1$ divides $M$ and that $q-1$ does not divide $M$ . As a result, Pollard’s p-1 calculation ends at $38!$ . $\square$

Example 3
Factor the number $N$ = 30,069,476,293, which is a product of two prime factors.

The preceding two examples show that the Pollard p-1 calculation usually needs to go up to the factorial corresponding to the largest prime factor of $p-1$ (or $q-1$ ). In this example, we show that the choice of the base $a$ also matters, though it is not a choice we can make at the outset. We use $15!$ to start and make the following calculation.

$\displaystyle 2^{15!} \equiv 2640468470 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{15!}-1,N)=1$
$\displaystyle 2^{16!} \equiv 11548010587 \ \text{mod} \ N$ …………… $\text{GCD}(2^{16!}-1,N)=1$
$\displaystyle 2^{17!} \equiv 17457718327 \ \text{mod} \ N$ …………… $\text{GCD}(2^{17!}-1,N)=1$
$\displaystyle 2^{18!} \equiv 28780043158 \ \text{mod} \ N$ …………… $\text{GCD}(2^{18!}-1,N)=1$
$\displaystyle 2^{19!} \equiv 19852010325 \ \text{mod} \ N$ …………… $\text{GCD}(2^{19!}-1,N)=104729$

With the above calculation, we have $N$ = 104,729 x 287,117. With $p$ = 104,729 and $q$ = 287,117, we examine the factorizations of $p-1$ and $q-1$ .

$p-1=2^3 \times 13 \times 19 \times 53$

$q-1=2^2 \times 179 \times 401$

With the largest prime factor of $p-1$ being 53, why do we not have to calculate all the way to $53!$ ? The answer is that the base 2 in this example is a good choice for a base. The order of 2 modulo $p$ is 1976, much smaller than $p-1$ = 104,729. In this case, the base 2 is not a primitive root modulo $p$ . If we use a base $a$ that is a primitive root modulo $p$ , then the calculation would extend all the way to $53!$ . Since we do not know the value of $p$ before the calculation, choosing a good base is not something we can do. Thus, there is an element of luck in the Pollard p-1 method.

We now analyze this situation further by showing how the number 1976 is determined. To determine whether the number 2 is a primitive root modulo $p$ = 104,729, we need to evaluate the exponentiation $2^{\frac{p-1}{t}}$ modulo $p$ for all prime factors $t$ of $p-1$ .

. $\displaystyle \frac{p-1}{2}=52364$ ………….. $2^{52364} \equiv 1 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{13}=8056$ ……………. $2^{8056} \equiv 2522 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{19}=5512$ ……………. $2^{5512} \equiv 48162 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{53}=1976$ ……………. $2^{1976} \equiv 1 \ \text{mod} \ p$

If the number 2 were to be a primitive root, the results on the right side of the above calculation should be all not congruent to 1. In this case, the smallest exponent of 2 is 1976, which is the order of 2 modulo $p$ . In the above explanation of Pollard’s p-1 method, we say that we need to find $M$ such that $p-1$ divides $M$ but $q-1$ does not divide $M$ . Note that $p-1$ is this case is 104,828. In this example, we do not need to go this high, we just need to find $M$ such that 1976 divides $M$ . Our calculation shows that $M$ can be $19!$ . Again, this is an element of luck. This analysis can only be performed after the fact.

For comparison, let’s use a primitive root as the base. The number 12 is a primitive root modulo $p$ . We start with $19!$ and find that the GCD is 1. Based on the analysis in the preceding paragraph, we know the calculation likely needs to go up to $53!$ . So we skip from $19!$ to $52!$ .

$\displaystyle 12^{19!} \equiv 14031100377 \ \text{mod} \ N$ …………… $\text{GCD}(12^{19!}-1,N)=1$

$\displaystyle 12^{52!} \equiv 29099088982 \ \text{mod} \ N$ …………… $\text{GCD}(12^{52!}-1,N)=1$
$\displaystyle 12^{53!} \equiv 10843640661 \ \text{mod} \ N$ …………… $\text{GCD}(12^{53!}-1,N)=104729$

The last calculation shows that if we happen to use a primitive root (modulo one prime factor $p$ of $N$ ) as the base, the calculation may take longer. Ideally, we would like to use a base that has small order. Of course, this is not a choice we can make ahead of time. $\square$

Example 4
In this example, we use Pollard’s p-1 method to factor $N$ = 21,428,053, which is a product of two prime numbers.

We start with $30!$ and compute $2^{30!}$ modulo $N$ . The GCD values of $\text{GCD}(2^{n!}-1,N)$ are all 1’s even after a long series of calculation. Thus, we only show that selected steps to give a sense of the amount of effort.

$\displaystyle 2^{30!} \equiv 16728337 \ \text{mod} \ N$ ……………. $\text{GCD}(2^{30!}-1,N)=1$

$\displaystyle 2^{100!} \equiv 8115587 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{100!}-1,N)=1$

…………..

$\displaystyle 2^{150!} \equiv 18994160 \ \text{mod} \ N$ …………… $\text{GCD}(2^{150!}-1,N)=1$

…………..

$\displaystyle 2^{200!} \equiv 57349 \ \text{mod} \ N$ ……………….. $\text{GCD}(2^{200!}-1,N)=1$

…………..

$\displaystyle 2^{250!} \equiv 11825174 \ \text{mod} \ N$ …………… $\text{GCD}(2^{250!}-1,N)=1$

…………..

$\displaystyle 2^{260!} \equiv 5105076 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{260!}-1,N)=1$
$\displaystyle 2^{261!} \equiv 18320624 \ \text{mod} \ N$ …………… $\text{GCD}(2^{261!}-1,N)=1$
$\displaystyle 2^{262!} \equiv 16958949 \ \text{mod} \ N$ …………… $\text{GCD}(2^{262!}-1,N)=1$
$\displaystyle 2^{263!} \equiv 15751435 \ \text{mod} \ N$ …………… $\text{GCD}(2^{263!}-1,N)=5261$

The calculation shows that $N$ = 4073 x 5261. Now that we have the answer, we can analyze the process. Here’s the factorization of $p-1$ and $q-1$ where $p$ = 5261 and $q$ = 4073.

$p-1=2^2 \times 5 \times 263$

$q-1=2^3 \times 509$

The largest prime factor of $p$ is 263. The largest prime factor of $q$ is 509. This indicates that the calculation would involve $263!$ . The base 2 is a primitive root modulo 5261, ensuring that the calculation would need to go to $263!$ . Note that the composite $N$ in this example is much smaller than the ones in Example 2 and Example 3. Yet this example requires a lot more effort because $p-1$ (or $q-1$ ) has larger prime factors. This example reinforces the point that Pollard’s p-1 algorithm excels in factoring $N$ where $p$ is one of the prime factors of $N$ and $p-1$ has small prime factors. The smaller the prime factors of $p-1$ , the lower the amount of calculation. $\square$

Fermat Numbers

The composite numbers $N$ in the four examples in the preceding section are only illustrations for Pollard’s p-1 factorization algorithm. The numbers in these examples are small enough so that the trial division, when programmed in a computer, is workable as a factorization algorithm. In this section, we mention two examples of factorization that are in much larger scale than the above examples. Both examples involves the 12th Fermat number.

A Fermat number is a positive integer of the form $F_n=2^{2^n}+1$ where $n$ is a non-negative integer. Due to their large sizes, Fermat numbers are difficult to factor or to check for primality. Pepin’s test is a primality test for Fermat numbers (see here). According to the Wikipedia entry on Fermat numbers (see here), only the Fermat numbers $F_0$ to $F_{11}$ have been completely factored as of November 2021. Currently, six factors of $F_{12}$ have been discovered so far (see here).

Edouard Lucas in 1878 proved that every factor of the Fermat number $F_n$ , $n \ge 2$ , is of the form $k \times 2^{n+2}+1$ . A number of this form is called a Proth number. One prime factor of $F_{12}$ was discovered by R. Baillie in July 25, 1986, which is a 16-digit number. The following is the 16-digit prime factor $p$ along with the factorization of $p-1$ .

$p=76668221077 \times 2^{14}+1=1256132134125569$

$p-1=2^{14} \times 7^2 \times 53 \times 29521841$

Note that the largest prime factor of $p-1$ is 29,521,841, which is small enough relatively speaking. As a result, Pollard’s p-1 method was used in this case.

A 54-digit prime factor of $F_{12}$ was discovered by M. Vang, Zimmermann & Kruppa in March 27, 2010. It is expressed as $p=m \times 2^{15}+1$ where $m$ is a 50-digit prime number. Thus, the largest prime factor of $p-1$ is the 50-digit prime number $m$ . This prime factor was discovered using the Elliptic Curve Method (ECM) and could bot have been discovered using Pollard’s p-1 method. This example reinforces the idea that for Pollard’s p-1 method to work, $p-1$ needs to be made up of “small” prime factors for one prime factor $p$ .

Remarks

One point worth mentioning is that when we obtain a new factor using Pollard’s p-1 method, we need to check its primality, e.g., using a primality test such as the Miller-Rabin test. The numbers $N$ in the four examples given above are stated as a product of two primes. As a result, any factor that results can be assumed a prime. When the factoring effort has no known facts given, we cannot just assume any factor produced is a prime number.

The four examples above are structured in a way that each $N$ is a product of two primes (i.e., they are semiprimes). Pollard’s p-1 method can certainly be used for factoring numbers that have more than two prime factors. Just that each resulting factor should be further factored if it turns out to be not a prime.

Pollard’s p-1 algorithm has elements of luck involved. For example, if we happen to use a starting point for $n!$ that is not far from the factorial that produces a prime factor, the algorithm works spectacularly well. On the other hand, if we happen to use a base $a$ that has a lower order modulo one of the prime factors, the calculation may stop as a lower value of $n!$ . Of course, the amount of calculation depends on the magnitude of the prime factors of $p-1$ . If the largest prime factor of $p-1$ is a 50-digit number as for one prime factor of the Fermat number $F_{12}$ as indicated in the preceding section, Pollard’s p-1 method should not be considered. On the other hand, another factor of the Fermat number $F_{12}$ was obtainable using Pollard’s p-1 because the largest prime factor of $p-1$ is only an 8-digit number. When doing exercise problems on factoring using Pollard’s p-1 method, the amount of effort varies. The $n!$ that produces a factor may be in the range of 10s or 100s or even 1000s for $n$ . The decision of how high of a factorial we are willing to go is based on how much effort we wish to expend or whether the computational resources at our disposal are up to the challenge.

The study of factoring adds to our understanding of cryptosystems whose security relies on the apparent difficulty of factoring large numbers. For example, with insight obtained from knowing Pollard’s p-1 method, when setting the modulus $N=p \times q$ for RSA, we can improve the security by choosing $p$ and $q$ such that $p-1$ and $q-1$ have at least one large prime factor. When the primes $p$ and $q$ are large, the resulting RSA public key may seem secure. If $p-1$ and $q-1$ have small prime factors, it is a vulnerability Pollard’s p-1 factoring method can exploit.

$\text{ }$

Dan Ma Pollard’s p-1 factoring algorithm

Dan Ma Pollard’s p-1 factoring method

Daniel Ma Pollard’s p-1 factoring algorithm

Daniel Ma Pollard’s p-1 factoring method

Mathematical Cryptography

focusing on the math in public key cryptography

Tag Archives: Pollard's p-1

Pollard’s p-1 factorization algorithm