Ben Laurie wrote: >William Knowles wrote: >> Prime numbers (such as 1, 5, 11, 37...) are divisible only by >> themselves or 1. While smaller prime numbers are easy to make out, for >> very large numbers, there never had been a formula for "primality >> testing" until August 2002. > >Doh! This is so untrue. The point is that they discovered a test that >wasn't NP, for the first time. OK, so its P but with a vast constant, >but even so, there must be a point at which it gets better than the best >NP methods. I wonder if anyone's worked out where that point is?
If you compare to randomized algorithms, I suspect the answer is "never". There are randomized algorithms that run in polynomial time that have been known for many years. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
