5
$\begingroup$

Is there a polynomial-time algorithm to find a prime larger than $n$?

If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will find a prime in polynomial time (in $\log n$) because AKS runs in polynomial time and Cramér's conjecture guarantees $O((\log{n})^2)$ primes to test.

Without assuming Cramér's conjecture, and without requiring that the prime to be found is the next prime following $n$, only that it is larger than $n$, can such a prime be found in time $O((\log{n})^k)$ for some $k$?

This question is motivated by some thoughts I wrote about in the comments on this answer by Gerry Myerson.

  • 3
    Related [Deterministic Methods to Find Primes](http://terrytao.files.wordpress.com/2011/02/polymath.pdf).2012-11-02
  • 0
    I read through the paper; it considers exactly this problem as well as some related ones and it is said to be open. I would like to accept this as an answer.2012-11-03
  • 0
    Is this asking whether to find the next prime larger than $n$, or drawing a prime larger than $n$ following a specific distribution? Because if not, Maurer's algorithm with a suitable lower bound should get the job done.2015-01-19
  • 0
    (technically, it is probabilistic, but takes finite time and always returns a prime along with a provable primality certificate)2015-01-19

1 Answers 1