**There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size**. That is sanctioned by [FIPS 186-4][1], appendix B.3; specifically, wording in B.3.1 item A: > Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], > $p$ and $q$ with lengths of 1024 or 1536 bits may be generated; > $p$ and $q$ with lengths of 512 bits **shall not** be generated using these methods. > Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the > conditions based on auxiliary primes. 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. The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against [Pollard's p-1][2] factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including [GNFS][3] and [ECM][4]) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against [Williams' p+1][5] factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later]. Determining _quantitatively_ when we can dispense of precautions against Pollard's p-1 is not trivial! - 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][6], a significant time is spent in Pollard's p-1, with [great success][7]); 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][8]), and unbalanced RSA as in [RSAP and SPAKE/ALIKE][9], 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]. [1]: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf [2]: http://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm#Algorithm_and_running_time [3]: http://en.wikipedia.org/wiki/General_number_field_sieve [4]: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization [5]: http://en.wikipedia.org/wiki/Williams%27_p_+_1_algorithm [6]: https://gforge.inria.fr/projects/ecm/ [7]: http://www.loria.fr/~zimmerma/records/Pminus1.html [8]: http://www.emc.com/domains/rsa/index.htm?id=2125 [9]: http://crypto.stackexchange.com/q/15553/555 [10]: http://en.wikipedia.org/wiki/Dickman_function [11]: http://www.loria.fr/~zimmerma/records/Pminus1.html [12]: http://eprint.iacr.org/2010/006.pdf [13]: http://rd.springer.com/chapter/10.1007/978-3-642-14992-4_11