Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
Thank you very much for both of your answers ! –  Awake Zoldiek Oct 8 '12 at 0:40

As far as I know, the AKS primality test is the most effective known method to decide if a large number picked at random is prime or not.

If we pick a large number $N$, the probability it is prime is about $\frac{1}{\ln (N)}$. Thus, if you look for a prime number with $t$ digits, if you pick about $t \log(10)$ $t$-digit numbers at random, there is a pretty big chance one will be prime...The time involved is usually reasonable for a computer....

share|improve this answer
AKS is seldom used in practice. When it comes down to it, algorithms that were present before it - especially the Miller-Rabin algorithm and its variants - are much faster, even if AKS is asymptotically better (or just deterministic). –  Yoni Rozenshein Oct 7 '12 at 23:55

Neither of the algorithms mentioned in the two previous answers are used to find record large primes. Lucas-Lehmer has the advantage that it is as fast as Miller-Rabin, and deterministic (it guarantees primality/compositeness rather than being probabilistic). However it is severely limited in that it only works on numbers of the form $2^n-1$ (Mersenne numbers). All of the last dozen or so record primes have been Mersenne primes located by massive volunteer effort and verified by Lucas-Lehmer test.

As far as I know, RSA has no prime number challenge, but it does have factoring challenges (which require considerably different algorithms). Are you perhaps thinking of the EFF cooperative computing awards for finding large primes?

share|improve this answer
yes, I kind of mistakenly took the RSA challenge for the EFF one. Sorry about that. –  Awake Zoldiek Oct 8 '12 at 10:12
but shouldn't better to generate primes AT RANDOM ??¿ i mean if i were a 'hacker' i first would study all the prime generating algorithms to crack codes :D :D so perhaps a prime-generating algorithm is not quite safe. –  Jose Garcia Oct 8 '12 at 10:45
@JoseGarcia My point is that the method for generating primes depends on your intent. It could be for cryptography, for amusement, for record-breaking, etc. And the standards for testing could vary in strictness (probabilistic vs provable primes). –  Erick Wong Oct 8 '12 at 14:12

Your Answer


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.