# How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

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.

• Depends on the algorithm, its implementation, the hardware and the number itself, really. It's not easy to say.
– Juho
Jan 15 '20 at 12:08
• 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. Jan 15 '20 at 12:24
• 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. Jan 15 '20 at 14:20
• @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).
– Juho
Jan 15 '20 at 14:52
• 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? 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.

• 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? Jan 15 '20 at 22:10
• 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. Jan 16 '20 at 7:49
• 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. Mar 21 '20 at 7:49