What prime number generating algorithms are used? 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].
 A: 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. 
A: 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....  
A: 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?
