[12308] in cryptography@c2.net mail archive
Re: Prime numbers guru 'factors' down success
daemon@ATHENA.MIT.EDU (David Wagner)
Mon Jan 20 14:42:23 2003
X-Original-To: cryptography@wasabisystems.com
X-Original-To: cryptography@wasabisystems.com
X-Envelope-To: cryptography@wasabisystems.com
To: cryptography@wasabisystems.com
From: daw@mozart.cs.berkeley.edu (David Wagner)
Date: 20 Jan 2003 18:32:23 GMT
X-Complaints-To: news@abraham.cs.berkeley.edu
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@wasabisystems.com
