6 ms·
There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
by openasocket 11y ago
There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
- zitterbewegung 11y agoJust because there are exact tests doesn't make the AKS primarily test usable in the real world because of constant factors . Using Fermats little theorem for primality testing is fine because the probably of encountering a Carmichael number is very low.
- openasocket 11y agoYou're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, such as ECPP. Here's some of the largest primes found using ECPP: http://primes.utm.edu/top20/page.php?id=27 http://primes.utm.edu/top20/page.php?id=27 Note the largest there is 30,950 digits, which is about 102,813 bits unless I did my math wrong, so I bet it is usable for 1024-bit numbers. Non-exact methods are much much faster of course, but when you really really need exactness it is an option.
- schoen 11y agoThat does seem pretty efficient for numbers of this size; thanks for the example!
- jcoffland 11y agoSeems like a Carmichael number could be a good choice for an attacker. This would make your chances of encountering a Carmichael number quite high. You have to consider who's choosing the number. Or do I have it wrong?
- pbsd 11y agoOnly the simple Fermat tests are vulnerable to Carmichael numbers. The test which is used in practice, Rabin-Miller, is not vulnerable to them. In fact, if you assume the extended Riemann hypothesis is true, (log n)^2 iterations of Rabin-Miller are sufficient to prove primality.
- schoen 11y agoHow efficient might this be compared to other approaches for searching for Riemann hypothesis counterexamples? Is there a one-to-one relationship between direct Riemann counterexamples and composite numbers that pass (log n)² Rabin-Miller tests?
- pbsd 11y agoI am not familiar with all the ways the GRH can be disproven, but Miller-Rabin doesn't strike me as the most efficient, with its running time of O((log n)^4) for each attempt. I am not sufficiently competent to say whether a GRH counterexample also directly results in a MR counterexample.
- gchpaco 11y agoIn addition to what pbsd said, Carmichael numbers are incredibly rare. Your odds of stumbling across one by chance are lower than the odds of a cosmic ray flipping the bit of memory that causes you to believe you have stumbled across one, as I recall.
- schoen 11y agoI 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]