Re: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36056] Re: [mg36023] RE: [mg35992] Notebook for Primes
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Wed, 14 Aug 2002 05:35:23 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Well, this depends on the meaning of "polynomial" time. The running time of the Sieve of Eratosthenes is Sqt[n], but time complexity in the case of prime testing is always expressed in terms of log[n], so the sieve is considered exponential. I think the fastest deterministic test is the Rabin-Miller which is (I am not quite sure of that) Log[n]^2, but it depends on the unproved Generalized Riemann Hypothesis. Agrawal, Kayal and Saxena give a Log[n]^12 algorithm, but they also give a complete proof of its correctness. I have not read their paper but assuming that it is correct, the algorithm is certainly much faster than the sieve. On the other hand the GRH is most probably true... On Tuesday, August 13, 2002, at 06:22 PM, DrBob wrote: > The oldest algorithm for testing primes... the Sieve of Eratosthenes... > is polynomial and deterministic. It's simply too slow to use, just like > the one at the attachment. > > Bobby > > -----Original Message----- > From: Jeff Dillon [mailto:jeffdi at fidalgo.net] To: mathgroup at smc.vnet.net > Subject: [mg36056] [mg36023] [mg35992] Notebook for Primes > > > Is there a publicly available Mathematica 3.0 notebook that implements > the Primes is in P? > > http://www.msnbc.com/news/792126.asp > > > > >