3 ms·
It’s worth mentioning that the discovery of a deterministic polynomial time algorithm to determine primality is pretty recent, 2002. https://en.m.wikipedia.org/
by ouid 8y ago
It’s worth mentioning that the discovery of a deterministic polynomial time algorithm to determine primality is pretty recent, 2002. https://en.m.wikipedia.org/wiki/AKS_primality_test https://en.m.wikipedia.org/wiki/AKS_primality_test
- SilasX 8y agoIt's also worth mentioning that AKS didn't have much impact on practical cryptography. The probabilistic algorithms for checking primality are (and were) much faster, and have a tolerably-low chance of failure in selecting prime numbers for crypto. I bring this up because, one (heuristic) reason to believe BPP=P is that, in practice, moving PRIMES from BPP to P didn't make a difference.
- ouid 8y agosomeone (recently?) constructed a composite number which failed miller rabin for 400 iterations or something.
- andreasscherman 8y agoTo help anyone who was as confused as I about this being the first polynomial time algorithm. To me, even the naïve primality test is a polynomial time algorithm over the target number. However, here the AKS primality test is a polynomial time algorithm over the number of digits in the target number, which of course is different!
- allenz 8y agoYes, time complexity is based on the length of the input to a Turing machine. For example, integer factorization is a hard problem because all known algorithms are roughly exponential in the number of bits.