Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Related Deterministic Methods to Find Primes. – 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 '15 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 '15 at 14:07
up vote 1 down vote accepted

This is Rick Sladkey's comment as a CW answer. An algorithm is given in this paper: "Deterministic Methods to Find Primes".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.