Possible Duplicate:
Finding a prime greater than a given bound


Does there exist

  • a polynomial $q$
  • and a deterministic polynomial time algorithm $A$

    such that for all sufficiently large $n$, we have:

    $A(n)$ outputs a prime $p$ s.t. $n \leq p \leq q(n)$. (Note $n$ is stored in binary, so $A$ must run in $poly(\log n)$ time.)


Suppose that for some derandomization task we need to be able to construct primes. This rules out the "guess a random number + check" approach since we can't use randomness.


  • $\begingroup$ AFAIR, it is open if that is possible. $\endgroup$
    – Kaveh
    Jan 21, 2013 at 4:44
  • $\begingroup$ @Kaveh: You're right, this is an exact duplicate. Should I delete this question or wait for it to be closed? $\endgroup$
    – user13350
    Jan 21, 2013 at 6:14
  • $\begingroup$ Closed as a duplicate. $\endgroup$
    – Kaveh
    Jan 21, 2013 at 6:28