Take the 2-minute tour ×
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.

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|improve this question
3  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.