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

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.

-
– Rick Sladkey Nov 2 '12 at 6:40
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. – Dan Brumleve Nov 3 '12 at 17:28
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. – Thomas Jan 19 at 13:54
(technically, it is probabilistic, but takes finite time and always returns a prime along with a provable primality certificate) – Thomas Jan 19 at 14:07