What algorithm can be used to check whether a large number is prime?

Question

Programming

Are there methods to guarantee that a number is prime without the need for a complete "brute force"?
Everywhere there are either the method "to divide by all numbers less than this" or probabilistic (do not guarantee correctness), there is no other way to determine?
If for numbers up to 100 characters you can still "sort through" at least half of everything, then with numbers of hundreds of thousands of characters this is a pointless undertaking, it seemed to me that there should be ways to determine this without the need to perform 10 ^ 100500 operations.

Answer 1

The layout is about the same. Let n be the length of the number, i.e. normal enumeration takes 2^{c * n}.
1) The Rabin-Miller probabilistic test can be implemented in O(kn^2 log n), where k is the number of attempts. The probability of a false positive error is 4^-k. With k=100, this value is so insanely small that it's more likely that your program will have a critical bug, the processor will make a calculation error, and the cracker will win the lottery and all this at the same time, than the number will turn out to be composite.
2) Deterministic AKS ( en.wikipedia.org/wiki/AKS_primality_test ). Runs in O(n^{6 + eps}). More interesting theoretically.
3) Elliptic Primality Test ( en.wikipedia.org/wiki/Elliptic_curve_primality). Empirically works in O(n^5). It is interesting that in case of success it returns a certificate of simplicity.

Answer 2

As an option: divide by all prime numbers not exceeding the square root of the given number.

Answer 3

It won't be done quickly. It is not for nothing that large prime numbers are used in cryptography. Even if you take into account the fact that you are not trying to factor out this goodness.

Answer 4

As far as I remember, this is a very difficult task, and for finding a prime number in a billion digits they give about half a million dollars. Dare)