Is it possible to determine in a reasonable time (hours \ days) whether a given number, with more than 1000 digits, is prime?

Question

Mathematics

The essence of the question is in the title, I know that there are many algorithms, but I wonder how long the procedure will take, say if there are 1 million. signs. The number is predetermined.

Answer 1

There are probabilistic tests, such as Rabin-Miller.

Answer 2

The speed of the probabilistic algorithm is approximately C*L^2*log(L), where L is the length of the number being checked, C is the number of tests (the probability of false positive will not exceed 4^(-C)). This is if you use ultra-fast multiplication algorithms. For a million signs, the time will be several trillion - and everything depends on the constant there. Will it be hours or days - it's hard to say.
If the number being tested is equal to the product of several known primes + 1, then the test can give a guaranteed result, but in this case C is equal to the number of numbers included in the product.

Answer 3

There is Agrawal's deterministic polynomial algorithm... for testing whether a number is prime.