2
$\begingroup$

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

3 Answers 3

3

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.

  • 0
    Thank you very much for both of your answers !2012-10-08
1

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

  • 2
    AKS is seldom used in practice. When it comes down to it, algorithms that were present be$f$ore it - especially the Miller-Rabin algorithm and its variants - are much faster, even if AKS is asymptotically better (or just deterministic).2012-10-07
1

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?

  • 0
    @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).2012-10-08