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:
- Mills' Constant - cannot be used, since the exact value of this number is unknown
- Rowland Recurrence Relation - cannot be used, since it is not monotonously increasing
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
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.