4

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.

user13768
  • 41
  • 1

1 Answers1

7

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

http://en.wikipedia.org/wiki/Prime_gap

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
  • 443
  • 3
  • 5
  • QiCheng how do you achieve $n^{0.525}$? – usul Feb 16 '13 at 00:42
  • $n^{0.525}$ is polynomial in $n$, but this is exponential in the size of the input, which is $\log n$. – a06e Feb 16 '13 at 01:51
  • 2
    Well, it is known that between $n$ and $n + n^{0.525}$ there must be a prime – QiCheng Feb 16 '13 at 05: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
  • 2
    In computational number theory, it is convention to use \tilde{O} for complexity. The "\log^6 n" disappear if you use \tilde{O}. In fact, the AKS time complexity of \log^6 n is also for \tilde{O}. – QiCheng Feb 16 '13 at 15:24