Re: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36047] Re: [mg36023] RE: [mg35992] Notebook for Primes
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 14 Aug 2002 05:35:15 -0400 (EDT)
- References: <200208130922.FAA10049@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg36047] [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 The sieve method is not polynomial in the size of the number. Polynomial in the number, yes, but exponential in the size (logarithm) of the number. The algorithm recently making waves appears not to be practical as yet. A variant proposed at the end of the draft article, based on an unproven conjecture of the authors, would possibly be viable as it would bring the suspected complexity exponent from 6 to 3. I imagine we will either hear of such improvements, or, at the least, get new pseudoprime algorithms, based on such variants of this new deterministic algorithm. Daniel Lichtblau Wolfram Research
- References:
- RE: Notebook for Primes
- From: "DrBob" <majort@cox-internet.com>
- RE: Notebook for Primes