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.


  • $\begingroup$ This sequence is the (2nd) Euclid-Mullin sequence: oeis.org/A000946 $\endgroup$ – jp26 Jun 15 '14 at 15:44
  • $\begingroup$ @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. $\endgroup$ – 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$.

The method you suggest is not practical since it requires factorization which is vastly harder than primality testing. As a ballpark it takes a few seconds to check if a 250-digit number is prime, where it would take thousands of processor-years to factor a number of this size (worst case -- a prime for the former and a hard semiprime in the latter). All the computers presently on the planet couldn't factor a number as large as the record prime, not even if they had been running since the Big Bang.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.