Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$?

There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking for something significantly more efficient; preferably, polynomial in $n$.

Also, if anyone knows of a proof showing a bound on the speed of such an algorithm (say, $n^4$), I would like to hear about it.

EDIT: It appears that polynomial in $\ln(n)$ makes more sense.

share|improve this question
    
If $n$ is odd, keep incrementing by 2 for as long as a test for compositeness returns true. If $n$ is even, add 1 first before using the procedure for odd $n$. –  J. M. Dec 22 '10 at 2:34
2  
Will any prime do? Or are you looking for the least such prime? In any case, see this previous question: math.stackexchange.com/questions/8865/… –  Aryabhata Dec 22 '10 at 2:36
    
I am unsure whether to close this as a dupe, there could be faster algorithms if any prime is sought. (For instance if we knew an upper bound for $n$, we could just hardcode it). –  Aryabhata Dec 22 '10 at 2:45
    
Trial division requires sqrt(n) queries "does m divide n?" (which can be tested in O(log n) time by Euclid's algorithm). There is always a prime between n+1 and 2(n+1). Hence, we can always find a prime greater than n in O(n*sqrt(n)*log n) time using J.M.'s algorithm. [you're probably after polynomial in log n] –  Douglas S. Stones Dec 22 '10 at 2:48
3  
I think you mean factoring n! + 1. –  Qiaochu Yuan Dec 22 '10 at 2:52

4 Answers 4

up vote 3 down vote accepted

Terence Tao has set up a "polymath project" which addresses exactly your question. Here is the relevant page:

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

It contains a list of conjectures, partial results and references. To sum it all up: At the moment the answer to your question is No.

share|improve this answer

Well theoretically speaking, there is a deterministic $\mathcal{O}(n \log ^{12} n)$ time algorithm.

By Bertrand's postulate, there is a prime $p$ guaranteed to satisfy $n \le p \lt2n$. (In practice, you should hit one much earlier than $2n$, owing to the prime number theorem).

Use the AKS primality testing program to test each of the numbers in the range $[n, 2n)$ and you will find one.

You can also try some sieving etc as suggested in the answers to this other question here: The least prime greater than 2000

share|improve this answer
    
It's been a while since I last looked into this subject (which was the time AKS was first published XD ): is AKS practical nowadays? –  J. M. Dec 22 '10 at 2:55
    
@J.M: I believe they got it down to $\log^6 n$, but I have heard it is still impractical. That is why I specifically said "theoretically speaking..." :-) –  Aryabhata Dec 22 '10 at 2:56
    
The time can be decreased to $O(n^{0.525+\varepsilon})$ due to Baker-Harman-Pintz 2001. –  Charles Sep 15 '11 at 18:04

There is an algorithm of complexity $O((\ln n) \cdot P(n))$ where $P(n)$ is the complexity of computing the prime counting function on n (usually denoted $\pi(n)$).

By Bertrand's postulate there is a prime in the interval $[n,2n]$ so you can do a binary search on it:

If $\pi\left(n+\frac{n}{2}\right)-\pi(n)$ > 1 there is a prime in the interval $\left[n, n+\frac{n}{2}\right]$, otherwise there is a prime in the interval $\left[n+\frac{n}{2}+1,2n\right]$ and so you obtain a smaller interval that contains a prime. Repeat the calculation on the new interval. The calculation for which of the 2 intervals to use needs time $O(P(n))$. Since each interval is half the size of the previous one the total number of calculations required is O(ln n).

Odlyzko's algorithm for $\pi(n)$ has complexity $O(n^{\frac{1}{2}})$. There is a link to a short description of it on the polymath page. So the overall complexity of this algorithm is $O((\ln n)n^{\frac{1}{2}})$.

share|improve this answer
1  
Isn't it $O(n^{0.5+\varepsilon})$? In that case the $\varepsilon$ subsumes the $\log n$ term entirely. –  Charles Sep 15 '11 at 18:07

Polynomial in $n$ is not efficient because the input length (measured in bits) is $\log_2 n$ and so $n$ is exponentially large in relation to your input length.

So it is easy to find a prime number greater than $n$ in time polynomial in $n$ (e.g. with the answer from Moron).

If you are interested in a deterministic algorithm than the polymath project gives you the current known results.

But there is a randomized algorithm with time polynomial in $\log_2 n$ that gives you a prime greater than $n$. You pick a random number from the set $n, \ldots, 2n$ and check this number with AKS or Miller Rabin primality test. With the prime number theorem you can proof that there are enough primes in the set (for large $n$) and if you repeat this algorithm $O(\log_2 n)$ times you find a prime with high probability.

At the moment I cannot find a reference for a detailed proof for the randomized algorithm. But if you are interested I can look for it when I have more time.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.