Does this mean that we have a sort of bloom filter-esque test for primality? (ie, it will give you a guaranteed no in O(1) but you'll have to crunch numbers to get the yes?)
If so, are there implications for things that want to know "is it prime?" quickly? Crpytography comes to mind, for instance...
This catches most non-primes ;)
bool maybe_prime(x) { return x % 2 && x % 3 && x % 5 && x % 7; }
https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...
So speed improvements are welcome for academic use. Although this doesn’t look like it’s a game changer.
How? Just run Fermat's little theorem on multiple values of "a" until you feel comfortable. [1]
Why a majority? There are certain exceptions such as the Carmichael numbers to which we need to use slower algorithms to verify the primality of.
Note that I'm assuming the number of calls to an algorithm is constant since it would be naive to discount the size of the number you're testing.
What are the implications of this result? Off the top of my head I can only think of one: the problem of deciding whether a number is prime or not is in the complexity class P (decidable in polynomial time). [2]
How does this affect cryptography? I would say not by that much.
Why? The "hardness" of some forms of cryptography (asymmetric) isn't from the ability to determine primality of a number. It's from the ability of determining the factors of a number. [3] That problem itself has greater implications for the field.
The question of whether it is possible to do so in polynomial time on a classical computer is actually an open question in CS right now.
Note the emphasis on classical! Amazingly, there exist a polynomial time algorithm to do so on a quantum computer called Shor's algorithm. [4]
[1] https://en.wikipedia.org/wiki/Fermat_primality_test
[2] https://en.wikipedia.org/wiki/AKS_primality_test
https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...