The most efficient method for generating new prime numbers

What is the most efficient method for generating a prime number larger than the largest known prime number, and what is the complexity of this method?

Techniques considered:

I know that the largest prime number record is usually broken when a Mersenne Prime is found. This happens when a prime $N$ is found, such that $2^N-1$ is also prime. But I cannot see how to turn this into a method which would guarantee finding a larger prime number efficiently.

So the only algorithm that comes to mind is this:

• Set $P_1=2$
• Set $P_2=3$
• Run forever:
• Set $P_3=$ the largest prime factor of $P_1P_2+1$
• Set $P_1=P_1P_2$
• Set $P_2=P_3$

But due to step of calculating the largest prime factor, this algorithm is not very efficient.

Thanks

• This sequence is the (2nd) Euclid-Mullin sequence: oeis.org/A000946 – jp26 Jun 15 '14 at 15:44
• @jp26: Thanks. First of all, thinking about it again, I'm not so sure that this sequence yields only prime numbers (in fact, I'm pretty sure that it doesn't). Second, even if it did, it would still require an extremely long computation in order to find the next number in this sequence. – barak manos Jun 15 '14 at 15:53

Most numbers are (relatively) hard to check for primality. In order to find a record prime you need to select some special form which is easy to check. Mersenne numbers are the easiest to check, so they're a natural choice. Proth primes (those of the form $k\cdot2^n+1$ with $2^n>k$) are almost as easy, as are generalized Fermat numbers $k^n+1$.