You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ?
For example in cluster / cloud computing, parallel computing …etc.
I imagine that everyone has their own "custom" optimized versions of more known prime number generational algorithms but what are the "base methods" used to do so.
Thank you very much in advance !
edit: I hope that I used the right [tags].
Best Answer
Suppose we are interested in producing a prime near a very large number $M$. It is convenient to not bother testing for primality the multiples of small primes, like the even numbers! For the remaining numbers, test, one after the other, candidates using a "probable prime" test such as Miller-Rabin.
Miller-Rabin is very fast, and can be used to quickly rule out candidates.
If we are not too fussy, we can accept such a probable prime as prime. There is a possibility of being wrong, but if we make the probability of error less than say $10^{-100}$, effectively we have certainty.
Or else, after locating a number which is "almost certainly prime" via Miller-Rabin, one can use one of the relatively expensive primality tests to make sure.