Return to Answer

• There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
• There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].

• There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
• There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].

• There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
• There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM]. In the following I consider these parameters.

As a first-order approximation, the asymptotic run time of the simplest form of Pollard's p-1 attempting to factor one $N$ (product of at least two random primes of large specified sizes), assuming standard multiplication algorithms, is $\mathcal O(B\cdot\log B\cdot \log^2(N))$ where $B$ is a parameter.

With goods odds, the algorithm succeeds or fails depending on if a prime factor $p$ of $N$ is such that $p-1$ has all its prime factors less than $B$, or not.

Odds that a large random prime $p$ has all its prime factors less than $B$ can be approximated using the Dickman–de Bruijn function as $\rho(\log(p)/\log(B))$. We could approximate that as $\rho(u)\approx u^{-u}$ [that's valid within a factor of $3$ for $u\le9$].

According to a reputable source, a form of Pollard's p-1 was used to find a 189-bit factor $p$ of a (likely at-least) 595-bit number [the product of non-trivial factors of the 750-bit $5^{323}+2^{323}$], with the highest prime factor of $p-1$ a 48-bit value. I do not know the exact effort involved, but the context makes it probable that it was done with a single CPU of 2012 running for a moderate amount of time. Update: I reproduced that with GMP-ECM 6.4.4 + GMP 6.0.0 using echo '(5^323+2^323)/(7*647*3506059703*12364618943*108991369171*2724783836059)' | ./ecm -pm1 -timestamp -v 536870912 200000000000000 -maxmem 12000 that ran only 439s on a 2.7GHz Core i5, and found the expected non-trivial 57-digit $p$.

Thus it is entirely feasible to target $B=2^{48}$ for our 1248-bit $N$ [the $\log^2(N)$ term in the asymptotic difficulty increases it by a factor of only about $4$]. Odds that it is enough to find a random 352-bit prime $p$ are about $\rho(352/48)\approx2^{-21.7}$. With $k=2^{20}$ (about a million) target keys, odds of success become sizable (26%), for a modest effort of 50 CPU.years (extremely roughly and hypothetical, but to be compared to 2000 CPU.years in the landmark GNFS factorization of RSA-768, where it is estimated a 1024-bit $N$ would cost a thousand times more). And we have not even tried to optimize $B$! As the saying goes: attacks only get better, they never get worse.

I beg others to check, challenge, improve my very rough computations; but I think that I can safely conclude that for the parameters considered [moduli of 1248-bit with a 352-bit factor that has been chosen at random], trying Pollard's p-1 on a million available moduli (assuming factoring any one scores as a success) is a much better use of CPU time than using GNFS on a single modulus. Also, there is a formidable advantage to Pollard's p-1: the great ease of distributing the attack on independent commodity machines, when GNFS requires a heavily-connected supercomputer in the final step. Thus it is reasonable to implement measures to guard against Pollard's p-1 (and while we are at it Williams' p+1) with such parameters. This complicates the generation method proposed in SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract), which wants to encode identity informations in some bits of the modulus.

• There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
• There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication (I second that, at least when no more than $2^{30}$ keys are generated, and absent any regulatory requirement enforcing high confidence levels or directly precluding random primes).

According to a reputable source, a form of Pollard's p-1 was used to find a 189-bit factor $p$ of an at-least 595-bit number [the product of non-trivial factors of the 750-bit $5^{323}+2^{323}$], with the highest prime factor of $p-1$ a 48-bit value. I do not know the exact effort involved, but the context makes it probable that it was done with a single CPU of 2012 running for a moderate amount of time.

Thus it is not unreasonable to target $B=2^{48}$ for our 1248-bit $N$ [the $\log^2(N)$ term in the asymptotic difficulty increases it by a factor of only about $4$]. Odds that it is enough to find a random 352-bit prime $p$ are about $\rho(352/48)\approx2^{-21.7}$. With $k=2^{20}$ (about a million) target keys (thus correspondingly more work compared to our reference), odds of success becomes sizable. We have not even tried to optimize $B$; and as the saying goes: attacks only get better, they never get worse.

I conclude that for the parameters considered [moduli of 1248-bit with a 352-bit factor that has been chosen at random], it is quite reasonable to fear that trying Pollard's p-1 on all available moduli (for plausibly many of these) is a better strategy than using GNFS on a single modulus. Also, there is a formidable advantage to Pollard's p-1: the great ease of distributing the attack on independent commodity machines, when GNFS requires a heavily-connected supercomputer in the final step. Thus it is reasonable to implement measures to guard against Pollard's p-1 (and while we are at it Williams' p+1) with such parameters. This complicates the generation method proposed in SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract), which wants to encode identity informations in some bits of the modulus.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

According to a reputable source, a form of Pollard's p-1 was used to find a 189-bit factor $p$ of a (likely at-least) 595-bit number [the product of non-trivial factors of the 750-bit $5^{323}+2^{323}$], with the highest prime factor of $p-1$ a 48-bit value. I do not know the exact effort involved, but the context makes it probable that it was done with a single CPU of 2012 running for a moderate amount of time. Update: I reproduced that with GMP-ECM 6.4.4 + GMP 6.0.0 using echo '(5^323+2^323)/(7*647*3506059703*12364618943*108991369171*2724783836059)' | ./ecm -pm1 -timestamp -v 536870912 200000000000000 -maxmem 12000 that ran only 439s on a 2.7GHz Core i5, and found the expected non-trivial 57-digit $p$.

Thus it is entirely feasible to target $B=2^{48}$ for our 1248-bit $N$ [the $\log^2(N)$ term in the asymptotic difficulty increases it by a factor of only about $4$]. Odds that it is enough to find a random 352-bit prime $p$ are about $\rho(352/48)\approx2^{-21.7}$. With $k=2^{20}$ (about a million) target keys, odds of success become sizable (26%), for a modest effort of 50 CPU.years (extremely roughly and hypothetical, but to be compared to 2000 CPU.years in the landmark GNFS factorization of RSA-768, where it is estimated a 1024-bit $N$ would cost a thousand times more). And we have not even tried to optimize $B$! As the saying goes: attacks only get better, they never get worse.

I beg others to check, challenge, improve my very rough computations; but I think that I can safely conclude that for the parameters considered [moduli of 1248-bit with a 352-bit factor that has been chosen at random], trying Pollard's p-1 on a million available moduli (assuming factoring any one scores as a success) is a much better use of CPU time than using GNFS on a single modulus. Also, there is a formidable advantage to Pollard's p-1: the great ease of distributing the attack on independent commodity machines, when GNFS requires a heavily-connected supercomputer in the final step. Thus it is reasonable to implement measures to guard against Pollard's p-1 (and while we are at it Williams' p+1) with such parameters. This complicates the generation method proposed in SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract), which wants to encode identity informations in some bits of the modulus.