0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$ – user991 Jan 10 '15 at 22:05
1
$\begingroup$

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

I guess the answer is "not much CPU time at all," but how much exactly depends on the CPU, memory speed, algorithm chosen, system load/usage, ... etc. All of those messy details are abstracted away with the use of Big-O notation (as above), so I think that's a more useful viewpoint.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Agreed. For fun I hacked together a sub-par prime generator that discovers a random 1024 bit prime in 300ms and 4096 bit prime in 30 seconds (though the time distribution is hugely variable in this toy generator). $\endgroup$ – Thomas M. DuBuisson Jan 10 '15 at 21:46
  • 1
    $\begingroup$ @Reid : $\:$ This paper gives an intermediate approach. $\;\;\;\;$ $\endgroup$ – user991 Jan 10 '15 at 22:15
  • 1
    $\begingroup$ Would you do AKS for every candidate? Why not eliminate candidates with simpler tests first, then do AKS (or ECPP) once you know you have a prime? $\endgroup$ – K.G. Jan 11 '15 at 17:43
  • 2
    $\begingroup$ @ThomasM.DuBuisson The time distribution can be hugely variable on HSM's and smart cards as well, and I presume - or at least hope - that they don't use a toy generator :) For larger key sizes it can be fun waiting for RSA key pair generation on a smart card. $\endgroup$ – Maarten Bodewes♦ Jan 12 '15 at 15:40
  • $\begingroup$ @MaartenBodewes-owlstead Interesting. Thank you for the input and your continued attempts to beat better cryptography engineering into people on the Internet. We have been watching you (see link with text 'this hero'). $\endgroup$ – Thomas M. DuBuisson Jan 12 '15 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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