See this question. The comment by Brett Hale stated:
On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort.
What's actually the 'little extra effort'?
The procedure to do this is:
When we find our prime $p$, we know that $p-1$ will have $r$ as a factor.
Step 1 is comparatively cheap compared to original search from the prime $p$; we select an $r$ which is large (as far as factors of $p-1$ go), but is small compared to $p$.
Step 2 is the original prime search, with an additional condition. That additional condition doesn't actually slow it down; it doesn't make checking a candidate any more expensive, nor does it make it less likely that a candidate is actually prime.
Hence, the has little extra effort; step 1 is fairly cheap, and step 2 has no additional cost.
|show 2 more comments|