# Williams' $p+1$ in tandem with Pollard's $p-1$?

Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint for $p + 1$, it seems to me that it would be extremely unlikely for neither $p - 1$ nor $p + 1$ to be smooth. So if we were to construct, say, a tough 500-bit (RSA-type) semiprime such as

$n = pq = \$ 2218295966162666629041316944231086113195058068148716022472522769336934503490317077398434252307822130896437753111872862038992461352826985916137012449841,

where $p$ and $q$ are both "safe" primes to guarantee worst-case performance for the $p - 1$ algorithm (that is, $(p - 1) / 2$ and $(q - 1) / 2$ are both Sophie Germain primes), would it make sense to attempt the $p + 1$ algorithm after $p - 1$ had bailed out? In other words, is there anything to be gained by trying that before ECM or bringing out the "big guns" of QS or NFS?

Oh, and I also generated the above semiprime with $\frac{p}{q}$ large enough to thwart factoring via Fermat's difference of squares method:

$\left|p - \sqrt{n}\,\right| \gt \sqrt[4]{4n}$.

• 'The "big guns" of ECM...'; actually, ECM isn't that much more expensive than Pollards. The algorithm is effectively the same as Pollards, just over a pseudocurve instead of $\mathbb{Z}_n^*$; this means that each computation is an EC addition, rather than modular multiplication; that just means that the overall ECM algorithm runs a constant factor slower... – poncho Jun 5 '18 at 12:41
• For what it's worth, my "big guns" comment was kind of paraphrasing Richard A. Mollin's Introduction to Cryptography, 2nd Ed, (2007), p. 219. In this, he was specifically referring to the use of QS after trial division, DoS, p-1, and $\rho$ had failed to find small factors. He then suggests that ECM can also be used for this purpose in advance of QS. – Dave Schulman Jun 5 '18 at 14:55

• Yes, I agree. There's not much point using trial division, SQUFOF, $p - 1, p + 1, \rho$, or maybe even ECM on something like a 617-digit RSA modulus. For semiprimes like that, I see little choice other than GNFS with massive computing power and a great deal of time. I suppose there's always a small chance that one of the probabilistic algorithms might get lucky and come up with a spectacular factorization, but my understanding is that even the upper bound on the probability of that happening is still minuscule. – Dave Schulman Jun 5 '18 at 17:13