5 ms·
I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is
by schoen 11y ago
I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is incredibly impractical because the polynomial is ginormous, even though its asymptotic behavior is nice. So if you actually wanted to know if, say, a 1024-bit number was definitely prime, you wouldn't be able to run AKS on it in a "reasonable time" on a real computer.
- baby 11y agoI haven't actually studied to what extent the AKS tests are do-able. I always figured there would be no problem running one for a 1024 bits prime. Found this on SO: http://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests http://cs.stackexchange.com/questions/23260/when-is-the-aks-... Also, to further the discussion on probable vs provable: the probable tests are enough in our case because they tell us _provably_ if an integer is not a prime (that we care), but _probably_ if an integer is a prime (which we don't care here).
- taejo 11y agoThis is not conclusive, but the best deterministic primality test (an AKS variant by Pomerance and Lenstra) is 6th power. 1024^6 is quite large.
- deleted 11y ago[deleted]