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.

  • $\begingroup$ 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. $\endgroup$ Mar 2 '13 at 16:26
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Mar 2 '13 at 17:47
  • $\begingroup$ @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. $\endgroup$ Mar 2 '13 at 18:14
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Mar 2 '13 at 20:07
  • 2
    $\begingroup$ Ah, no, I was comparing apples to oranges: The algorithms I was timing were too different to make sense of comparing them. $\endgroup$ Mar 3 '13 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.