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 '20 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$ – Mateusz Mazurek Jan 15 '20 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 '20 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 '20 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$ – Rick Decker Jan 15 '20 at 16:19

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 '20 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 '20 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 '20 at 7:49

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.