Prime numbers guru 'factors' down success

[Anton Stiglic]

----- Original Message -----
From: "Ben Laurie" <ben at algroup.co.uk>
To: "William Knowles" <erehwon at c4i.org>
Cc: <cryptography at wasabisystems.com>
Sent: Monday, January 20, 2003 11:47 AM
Subject: Re: Prime numbers guru 'factors' down success


> 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?

Technically you can't say that.  P is in NP, so if a problem is found to be
in P, it's not out of NP.  Note as well that the *problem* is situated in a
complexity
class, not the *algorithm* that solves it.
It was known before Agrawal and al. result that primality testing was in ZPP
for example (a class "between" P and NP).
The following FAQ explains this in a bit more of detail:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html

But the core of Laurie's argument is correct, in that it's not true that
only since
Agrawal and al. result can we determine if large integers are primes or not,
allowing for exponentially small probability of errors there are previously
known
algorithms that do much better than the algorithm from Agrawal and al.

--Anton




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com