There are many different special-case factoring algorithms for when $(p,q)$ have some special structure.
Which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure?
TLDR: None in modern practice. Except when there's a regulatory requirement for such explicit precautions.
There is now a large consensus that for semi-primes of cryptographic interest (say at least 512 or is it 1024 bits), we need to consider no special-case factoring algorithm when we care about the expected cost of factoring (using classical computers/hardware) one particular semi-prime generated per a process where both factors $p$ and $q$ are primes each picked independently and roughly uniformly at random in the same interval $[a,b]$, when $a>b^{0.9}$ and $a<0.99\,b$. A common choice is $a=2^{(n-1)/2}$ and $b=2^{n/2}$, which is guaranteed to give an exactly $n$-bit semi-prime.
There's a lot of headroom in both fudge factors $0.9$ and $0.99$, which are out of my head. The condition $a>b^{0.9}$ ensures that the bit size of $p$ and $q$ is never too far apart, which optimizes resistance to ECM. $a<0.99\,b$ ensures that the interval is not overly restricted.
It is often added further range restrictions, and that's OK especially for large $n$. For example it can be added that $p$ and $q$ are $n/2$-bit primes with their respective top 4 bits set to 1110 and 1100, which gives absolute (rather than statistical) certainty that FIPS 186-4's requirement $\lvert p-q\rvert\;>\;2^{n/2-100}$ and required ranges are met for endorsed $n$, and complies to ETSI TS 102 176-1's suggestion $0.1<\lvert\log_2p-\log_2q\rvert<30$.
Note: The fudge factor 0.1 in ETSI's suggestion used to be 0.5, which was incompatible with FIPS 186. The whole suggestion seems obsolete.
The same selection rules is usually fine when we care about small (but still palatable) residual odds that the semi-prime is factored for a given effort. This is a significantly different metric though, and it can matter. E.g., it might be considered unacceptable that an adversary has 0.1% chance to succeed with \$1M cost in electricity, even though certain success for \$500M is acceptable. ECM's probability of success grows linearly with the computational effort, when that of GNFS remains essentially at zero until the necessary effort is spent. GNFS might thus be less a concern when considering residual odds.
The argument for the above choice of interval $[a,b]$ is that at the size $n$ considered, all known factorization algorithms worth consideration have their expected cost larger (and their residual odds of success for limited work lower) than GNFS or ECM:
- we know how to improve resistance to ECM, and did that by random choice in an interval $[a,b]$ with $a>b^{0.9}$
- we don't know how to improve resistance to GNFS for a given size $n$, other than by avoiding semi-primes amenable to SNFS, which is kept to negligible probability thanks to random choice in an interval with $a<0.99\,b$
- MPQS, variations (PPMPQS, PPSIQS..) and ancestors (QS, CFRAC..), as well a the rational sieve, require more work than GNFS, and the gap increases when $n$ grows
- Pollard's p−1 and William's p+1 have larger expected work than ECM for sizable fixed probability of success, given the order of magnitude of the factors and the fact they are randomly seeded.
Note: that does not quite hold for extremely small probability of success (more on that later).
- Pollard's rho is outclassed by ECM on all counts, given the order of magnitude of the factors.
- Whatever improvement of Fermat's method or trial division requires knowledge of the order of magnitude of one of the factor, and random choice in an interval $[a,b]$ with $a<0.99\,b$ give a wide margin against that.
Things are more muddy when we care about factoring $k$ semi-primes of size $n$, for large $k$ and $n$ not too large, especially any one among those semi-primes (rather than all). The later consideration matters to a system designer who wants assurance that no semi-prime among $k$ used will be factored (perhaps because there is no way to detect rogue use of a factored semi-prime, or no revocation list, which is common in Smart Card applications; or just because the excuse "that's only for one in 100 million devices issued" would be untenable from a public relations perspective, even if it makes perfect sense economically).
This "batch factorization" problem is much less studied, especially in the "any one among" variant. Daniel J. Bernstein and Tanja Lange's Batch NFS, in proceedings of SAC 2014, conclude that increasing $k$ allows asymptotic savings on the expected cost per factorization. However, that does not require a different method of choosing $p$ and $q$; and it tells nothing useful about the "any one among" variant.
We can't state with confidence that increasing $k$ leaves the expected effort for factoring any one among $k$ semi-primes unchanged, even if we additionally discount attacks with an overall negligible probability of success (which makes sense). We even have a hint of the contrary: when $k$ increases, the expected effort using Pollard's p-1 lowers; and there's a threshold when it beats ECM with random curves, which expected effort is independent of $k$.
Pollard's p-1 can be viewed as ECM on a special curve amenable to lots of optimizations. In practice, the strategy maximizing probability to factor a semi-prime (with randomly selected factors of about equal size) using the popular GMP-ECM program and some maximum amount of CPU time involves spending some sizable fraction of the effort with its built-in Pollard's p-1. The lower the CPU allowance (and the probability of success), the larger that fraction is. When we switch to factoring any one among $k$ such semi-primes for the same maximum amount of CPU time, the optimal proportion spent on Pollard's p-1 grows markedly with $k$. That's because we can afford to use less random curves. At some point ECM on general curves is not used at all.
In order to reach a situation where Pollard's p-1 is worth considerations, we would need to
- somewhat discount NFS and QS algorithms so that ECM and friend are back into competition (perhaps because moduli have more than two factors as in multi-prime RSA, or/and one of the factor is small as in unbalanced RSA, or we are trying to lower residual odds of success for adversaries that will not manage to reach the work threshold or RAM requirement necessary for NFS),
- and consider that an adversary is content factoring any one among many moduli.
Under such hypothesis, adding precautions in the generation of the semi-primes that block Pollard's p-1 could be beneficial to some degree (I wish I could make that quantitative). The same applies, to a lesser degree, for William's p+1. This may be why such precautions remain mandated by FIPS 186-4 section B.3 for 1024-bit semi-primes.
Notice that for Pollard's p−1 and William's p+1, such precautions are not implemented as checks (that would be too computationally intensive), but rather are built into the method by which the prime factors are derived.
