How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the number has been checked using AKS pirmality test and it's also given that log(n) is the lenght of the number to be verified.

  • 2
    $\begingroup$ Depends on the algorithm, its implementation, the hardware and the number itself, really. It's not easy to say. $\endgroup$
    – Juho
    Jan 15, 2020 at 12:08
  • $\begingroup$ But it's said that it took 1 hour for 10-digit so it's probably connected proportionally with the time it would take to find a 20-digit one, but I have absolutely no idea how to find that connection. $\endgroup$ Jan 15, 2020 at 12:24
  • 2
    $\begingroup$ Reality check: $2^{10}=1024$ and $2^{20}=1048576$. Assuming you are using a computer, then determining whether a number with $20$ binary digits is prime will take a fraction of a second, not an hour. $\endgroup$
    – gandalf61
    Jan 15, 2020 at 14:20
  • $\begingroup$ @MateuszMazurek What is "it"? And indeed, you can't infer anything from a single data point (not that you could really infer much with multiple points necessarily, but anyway). $\endgroup$
    – Juho
    Jan 15, 2020 at 14:52
  • 1
    $\begingroup$ This looks like a poorly-worded elementary exercise to me, of the form "Look up the timing function for the AKS primality test elsewhere in the text and use that as the basis for your answer." Is that what you're asking? $\endgroup$ Jan 15, 2020 at 16:19

1 Answer 1


Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation.

[1] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

  • $\begingroup$ What is n? Specifically, what is n with a 20 binary digit number? And for a 20 binary digit number, don't you think that can be done a lot faster? $\endgroup$
    – gnasher729
    Jan 15, 2020 at 22:10
  • $\begingroup$ n is the number that is tested. I guess "20 binary digit number" means $n < 2^{20}$, and yes I think the algorithm takes only a small fraction of a second in that case. $\endgroup$
    – Laakeri
    Jan 16, 2020 at 7:49
  • $\begingroup$ 20 binary digits, and you asked for hours: With brute force, divisibility by a single prime can be checked in maybe two nanoseconds, divisibility by all primes < 1024 in about 360 nanoseconds, which is about 0.1 nano hours or 100 pico hours. $\endgroup$
    – gnasher729
    Mar 21, 2020 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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