Its right there in the question. I'm just interested in the subject. Has it been shown that you will always need brute computation to know if a number is prime?
2026-04-07 14:16:06.1775571366
Will primes always have to solved with brute force?
190 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are two very different concepts here. One is proving that a number is prime. The other is factorisation if it isn't prime. The second is much harder and is the foundation of encryption algorithms.
Most of the primality tests and factorizations are NOT based on trial division: prime testing is usually based on the Fermat's little theorem, and the trick behind different tests is how to select which numbers to put into $a^p=a\mod p$ and how to avoid "fake primes" that aren't primes but satisfy the identity.
There are a lot of fast prime testing algorithms that are probabilistic: if they say the number isn't prime, it really isn't, or they say it's a probable prime (but they can't be sure). For instance, checking Fermat's little theorem for a couple of random $a$ is pretty good, but not exact. Miller Rabin's and Pollard's Rho (also factorizes the result) are like that. On the other hand, you have AKS test (very recently discovered, I remember when it was published) that is actually exact and runs in polynomial time.
And of course there is the Shor's algorithm for quantum computers, but that's a whole different mechanism of "cheating" the time complexity by computing many options at the same time (not possible classically).
So it really depends on what you mean by "brute force". It certainly isn't trivial to prove primality, and it's much harder to factorize a number, but I wouldn't call our current algorithms brute-force. They definitely take into account known theorems to make work easier.