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