# 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.

-
Thank you very much, again :-) –  phan Mar 2 '13 at 15:51
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. –  Henrick Hellström 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. –  poncho 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. –  Henrick Hellström Mar 2 '13 at 18:14
Ah, no, I was comparing apples to oranges: The algorithms I was timing were too different to make sense of comparing them. –  Henrick Hellström Mar 3 '13 at 12:17