Find next prime

What's the best known complexity for the following problem? Given a number $n$, return the smallest prime larger than $n$.

Clearly one can just test all the odd numbers large than $n$ in turn until you find one. You can use a probabilistic primality testing algorithm with one-sided error and then confirm any primes using a AKS if needs be. This is slow but uses small space. Alternatively one could us a sieve which will be faster but uses potentially very large space.

-
possible duplicate of Finding a prime greater than a given bound –  Tsuyoshi Ito Feb 15 '13 at 21:54
The linked question seems to insist the algorithm is deterministic and also answers a different question. I am looking for the next prime, not any prime greater than $n$. –  user13768 Feb 15 '13 at 21:57
I thought that you were looking for a deterministic algorithm, but I was wrong, as was apparent from your example. I agree that it is a different question from the linked one; at least I do not know how to reduce one to the other in either direction. My apologies. –  Tsuyoshi Ito Feb 15 '13 at 22:14

Heuristically there is a prime between $n$ and $n + log^2 n$ for any sufficiently large $n$, so yes there is a deterministic polynomial time algorithm, which works quite well in practice (but is heuristic).
I do not think that there is a known algorithm with provable polynomial time algorithm for this problem. The best provable complexity you can achieve is $n^{0.525}$.
QiCheng how do you achieve $n^{0.525}$? –  usul Feb 16 '13 at 0:42
$n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$. –  becko Feb 16 '13 at 1:51
Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime –  QiCheng Feb 16 '13 at 5:02
OK, but if we include lower-order stuff, more specifically with AKS this gives about $n^{0.525} \log^6 n$; that is, $b^6 2^{0.525b}$ on $b$-bit input. Unless there is an asymptotic improvement in which numbers you check? –  usul Feb 16 '13 at 13:55