4 ms·
> We have efficient provable tests for that: they tell you if p is prime or not and nothing else. I think this is a typo -- the efficient general-form tests ar
by schoen 11y ago
> We have efficient provable tests for that: they tell you if p is prime or not and nothing else.
I think this is a typo -- the efficient general-form tests are probable rather than provable.
https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...
- Filligree 11y agoKeep up the tests until you have ten or twenty nines of certainty. I'd call that proof.
- baby 11y agothen you should re-read the definition of a proof.
- Filligree 11y agoWhat more are you hoping for? Given a mathematical proof, the chance of an error in the proof is vastly larger than 10^-20.
- jibalt 11y agoIt's clear that you haven't read it at all: http://www.merriam-webster.com/dictionary/proof http://www.merriam-webster.com/dictionary/proof The fact of the matter is that the sort of Platonic definition of proof that you fantasize is impossible because it depends on certainty, which itself cannot be proven. The best we can do is fail to find an error in an alleged proof. Consider the proofreader's paradox: A proofreader can be prepared to swear, for any given page of a 1000 page book, that there are no typos on that page, but no proofreader is so foolish as to claim that there are no typos in the book.
- openasocket 11y agoThere 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.
- 11y ago
- eutectic 11y agoThey can provably tell you that a number is composite.
- bjornsing 11y agoFrom your own reference (https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...): "the usual randomized primality tests never report a prime number as composite". So I'd say that's probably what happened here (i.e p was reported composite by a randomized primality test and that would never have happened had it been prime).
- schoen 11y agoOh sure, I don't mean that there's uncertainty that this number is composite, just that in a formal sense there isn't "proof" that other numbers that passed, say, openssl -checks 100000 are prime. But I wouldn't consider it unsafe to use them for cryptography. The comment I was replying to referred to tests that "tell you if a number is prime or not", and the probable ones don't exactly always do that. :-)