# How much (home PC) CPU time is required to generate a prime number of a given size?

How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes?

Please note that the prime number computed should be immediately next to the given random number, e.g. if the random number is 15, the computed prime number should be 17.

I want to know approximate time range on a typical home computer for the above mentioned prime sizes.

• Since "the prime number computed should be immediately next to the given random number," the best known bounds on the time grow more quickly than the square-root of "the given random number". $\hspace{.55 in}$ – user991 Jan 10 '15 at 22:05

By the prime number theorem, the average (asymptotic) distance from a prime $p$ to the next prime is $\log p$. So, on average, one must test $\log p$ integers for primality before finding the next prime. However, $\log p$ grows very, very slowly: even for 1024-bit numbers, $\log p \approx 710$.
Primality testing is well-understood, and very fast algorithms exist. For example, per AKS primality test, there exists a deterministic primality test with runtime $\tilde{O}(\log^6 p)$. Since we would have to run this test for (on average) $\log p$ integers, the runtime ends up becoming $\tilde{O}(\log^7 p)$. That's if you want an asymptotically-fast, deterministic test; in practice something like Miller-Rabin will do better, with a runtime of $\tilde{O}(k\cdot\log^3 p)$.
• @Reid : $\:$ This paper gives an intermediate approach. $\;\;\;\;$ – user991 Jan 10 '15 at 22:15