Re: Re: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36065] Re: [mg36056] Re: [mg36023] RE: [mg35992] Notebook for Primes
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Thu, 15 Aug 2002 02:36:16 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I was much too simple minded in my assessments of all the algorithms mentioned below .I should have known it's not as simple as it seemed but after all its only a hobby:). The complexity of the Sieve of Erasthoteness is well known to be O(n) (this is stated, for example, in Knuth, "The Art of Computer Programming", vol 3, p. 617). The Miller-Rabin algorithm has complexity O(log(n)^5) (not log(n)^2), assuming the GRH is true. (It is also deterministic). The Agrawal, Kayal and Saxenaalgorithm has a proven complexity of O(log(n)^12) and a conjectured running time of O(log(n)^6). The the sieve is certainly not even a contender. However, as for practical implementation, it seems to me that Miller-Rabin is clearly preferable. If the GRH is true it is faster than the new one. And if you find it running slow ... well that's even better ... Andrzej On Wednesday, August 14, 2002, at 06:35 PM, Andrzej Kozlowski wrote: > 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: [mg36065] [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 >> >> >> >> >> > > > > Andrzej Kozlowski Toyama International University JAPAN