Prime numbers guru 'factors' down success

[David Wagner]

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 majordomo at wasabisystems.com