# Deterministic Prime Construction [duplicate]

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

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