1
$\begingroup$

Possible Duplicate:
Finding a prime greater than a given bound

Question

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.)

Context

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.

Known

$\endgroup$

marked as duplicate by Kaveh Jan 21 '13 at 6:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ AFAIR, it is open if that is possible. $\endgroup$ – Kaveh Jan 21 '13 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 '13 at 6:14
  • $\begingroup$ Closed as a duplicate. $\endgroup$ – Kaveh Jan 21 '13 at 6:28