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.
8
-
2$\begingroup$ Depends on the algorithm, its implementation, the hardware and the number itself, really. It's not easy to say. $\endgroup$– JuhoCommented 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$– Mateusz MazurekCommented 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$– gandalf61Commented 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$– JuhoCommented 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$– Rick DeckerCommented Jan 15, 2020 at 16:19
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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$ Commented 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$– LaakeriCommented 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$ Commented Mar 21, 2020 at 7:49