# In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?

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:

• Find a large prime factor $r$

• When searching for the prime $p$, look among numbers of the form $rk+1$

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.

• IME step 2 is more expensive in the sense that it is less likely, given a fixed prime $r$ and a randomly selected $k$ of a fixed size, a number of the form $rk + 1$ is a prime, compared to a completely random odd integer of the same size. I only have experimental evidence to support this conjecture, though. Mar 2 '13 at 16:26
• @HenrickHellström: that sounds unlikely. We know that asymptotically, for fixed $r$, $i$ relatively prime, the probability that $p = rk+i$ is prime (as $k$ goes to infinity) is $r / (\phi(r) \log p) \approx 1 /\log p$. In other words, the $i=1$ case is no less likely to yield a prime than any other value of $i$. Now, this is an asymptotic result, it's possible that something odd happens for the moderate values of $k$ we use; I just find that unlikely. Mar 2 '13 at 17:47
• @Poncho: Well, our results show that finding primes $p$ with $p-1$ having large prime factors might take about 10 times longer. Another possibility is that Rabin-Miller is more likely to return false positive in the first iterations for $p = rk + 1$, which would also cause a slow down. Mar 2 '13 at 18:14
• @HenrickHellström: Hmmmm, that's not my experience. It's been a few years, but I did try RSA key generation with and without "subprimes" (X9.31); my conclusion was that the 100 bit subprimes didn't slow down the key generation much at all. As for Miller Rabin, well, the cases where it is likely to return a false positive is if $\phi(n)/(n-1)$ was a simple rational number; making sure $n-1$ had a particular factor isn't likely to cause that. Mar 2 '13 at 20:07
• Ah, no, I was comparing apples to oranges: The algorithms I was timing were too different to make sense of comparing them. Mar 3 '13 at 12:17