# How fast can we find primes (number of computations needed+time for the computation too)

So, I know we can get a bound on how long it will take to find a large prime. For example, using the fact that between $N$ and $2N$ there must be a prime. And the fact that all numbers between are prime iff they do not have a divisor less than $\sqrt{2N}$. So, this gives us one bound on the amount of time needed. (Assume that we know all the primes less than $\sqrt{2N}$.) Then the number of computations is at most $N\sqrt{2N}$ to find one prime.

Can this result be improved? In general, how long (# of computations * time per computation) does it take to find a new prime of size $N$

edit: ***The number of computations is at most $N \ln \sqrt{2N}$ Using the PNT.

-
In practice, this bound is very bad! For something like the RSA algorithm, you need an algorithm which is polynomial in the number of bits in $N$, not $N$ itself (note that primality testing can be done in polylogarithmic time via the AKS algorithm, and there are other approaches (e.g. Miller-Rabin) if you allow probabilistic algorithms). – Akhil Mathew Mar 29 '11 at 17:09
@Akhil, can you offer a better bound? AKS below looks promising, but what is the number of computations needed for that? – picakhu Mar 29 '11 at 19:22
Dear picakhu, I don't know the best worst-case bound for a deterministic algorithm, but on average, if you keep trying random numbers in $[0, N]$, you'll need about $\log N$ trials to find a prime number. Each trial can be done in polylogarithmic space using either a randomized or deterministic algorithm. So, probably, you'll need polylogarithmic time. – Akhil Mathew Mar 30 '11 at 3:14
By the way, I'm sorry if I came across as somewhat dismissive above; the point is that, in practice, one often needs a way to get large primes whose size may be exponential (or the number of bits polynomial). One example: polynomial identity testing in arithmetic circuits (via the Schwarz-Zippel lemma, see amathew.wordpress.com/2011/03/06/…) or the interactive protocol for TQBF. Here, it is absolutely essential that finding a prime is efficient. – Akhil Mathew Mar 30 '11 at 15:29

## 1 Answer

The usual way to generate big primes is simply choose at random large numbers and test whether they are prime or not. The prime number theorem shows that you have a chance of about $\frac{1}{\ln n}$ to stumble on a prime that way, $n$ being your upper bound. In practice this can be (roughly) translated to "the number of failed attempts is the same order of magnitude as the number of digits in the prime you are attempting to generate", so a 2048-bit prime will take about 2,000 attempts even without any smart optimization - not that bad.

The main question is how to test that a number is prime. In practice, first attempt to divide by the first 100 primes or so. If that fails, run the Miller-Rabin test as it is very fast ($O(\ln ^3n)$). Miller-Rabin is probabilistic, so it might fail (tell you that a composite number is prime; never the other way around), but with the reasonable security parameters you can guarantee that the chance for an error is virtually nothing (even if you run Miller-Rabin for the rest of your lifetime, no error is expected).

If you must be 100% sure you have a prime, the AKS test will work, although it is much slower than Miller-Rabin. There are other methods of primality proving, such as the elliptic-curve test; they won't always work efficiently, but they're worth a try.

For further reading, try "Prime Numbers" by Crandall and Pomerance, which deals exactly with these topics.

-
what is the time it takes for AKS? Wiki was not kind to me. (or I missed something obvious) – picakhu Mar 29 '11 at 21:09
I do not know the state-of-the-art complexity (the algorithm was substantially improved since first presented), but I think it's about \ln^6 n. – Gadi A Mar 29 '11 at 22:29
Essentially quartic time due to Bernstein (and probably others) if you're willing to accept a random algorithm. Gadi is about right for deterministic algorithms. – Charles Apr 12 '11 at 3:43