I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from the ordinary finding primes problem, which I'll state as:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(k)$?
Equivalently, the weak version is that there is a deterministic algorithm to find a prime $p > 2^k$ which runs in time $F(k)$ on infinitely many inputs $k$. Another formulation of the weak problem is to determine the values of $\displaystyle\liminf_{p\rightarrow\infty}{\frac{L(p)}{\log_2(\log_2(p))}}$ and $\displaystyle\liminf_{p\rightarrow\infty}{\frac{L(p)}{\log_2(p)}}$ where $p$ is prime and $L$ is the Levin complexity.
I consider both problems to be defined with respect to the class of models of computation possessing a time-translation to a single-tape Turing machine satisfying $T' \in T^{1+o(1)} \cdot S^{O(1)}$, where $T$ is the time used in the other model and $S$ is the space. This class includes the various RAM models and multi-tape Turing machines. However, the equivalence is sharper than a polynomial time-translation, and we can witness a specific value of the time exponent with an algorithm satisfying $S \in T^{o(1)}$ in any model in the class. For example, searching an interval $[2^n, 2^n + 2^{\epsilon \cdot n})$ for a prime can be accomplished in time $2^{\epsilon \cdot n + o(n)}$ in all of these models because the AKS test is simultaneously in subexponential time and subexponential space. But we won't be able to place the AKS test itself in a particular time class like $n^{6+o(1)}$ unless we can adapt it to simultaneously use space $n^{o(1)}$, until then the best we can say is that its runtime is $n^{O(1)}$ in every model. If either finding primes problem can be solved in polynomial time, assuming model-invariance won't make it any harder to prove that, and (suspending disbelief) it can only help to prove a lower bound on the exponent of exponential-time algorithms. It's plausible that it would present an obstruction to improving the exponential upper bound — for example, an algorithm that finds a prime $p > 2^k$ using $p^{\frac{1}{3}}$ time and $p^{\frac{1}{3}}$ space on some particular machine wouldn't qualify as an improvement under model-invariance. That's because the time exponent doesn't translate when the space is exponential — $\frac{1}{3}$ becomes $\frac{b+1}{3}$ after a $T' = T \cdot S^b$ time-translation. The exponential-time algorithms I refer to below are all in subexponential space anyway so this issue doesn't seem to actually come into play.
For the ordinary version, all we know is $F(k) \in 2^{0.525 \cdot k + o(k)}$, and I haven't been able to find any better bound for the weak version.
My understanding from the polymath page is that we don't know if having factoring for free can help us find primes. Can it help us find primes infinitely often?
An attractive aspect of the finding primes problem is that there are many conjectures which imply improvements. For example, the Riemann hypothesis puts $F(k) \in 2^{\frac{k}{2} + o(k)}$, Cramér's conjecture implies $F(k) \in k^{O(1)}$, and $\text{P}=\text{NP}$ implies $F(k) \in k^{O(1)}$. For my version of the problem, we additionally have that infinitely many Mersenne or Fermat primes gives $F(k) \in k^{O(1)}$, infinitely many $n^2+1$ primes implies $F(k) \in 2^{\frac{k}{2}+o(k)}$, and Bunyakovsky's conjecture implies $F(k) \in 2^{o(k)}$. Some other conjectures have similar implications. A world where we can't find primes infinitely often would be a very weird place, even weirder than one where we just can't find primes!
That is my main motivation behind studying this problem, to try and understand what that world would be like.
I'm looking for more information about finding primes infinitely often. In particular, is there any better time bound than what is known for the ordinary version? I haven't found it discussed in the polymath threads or elsewhere, and I haven't identified any open problems that any improvement implies, despite all the open problems that imply improvements. So for all I know, there's a simple and provably fast algorithm that I just can't think of myself.
