Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 4 down vote favorite

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'?

share|improve this question

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
Thank you very much, again :-) – phan Mar 2 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 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 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 at 18:14
1  
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 at 12:17
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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