Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2009-01-06, 14:38   #1
CRGreathouse's Avatar
Aug 2006

176116 Posts
Default Sieving for primes

I was considering various ways to sieve for primes (like the Sieve of Eratosthenes), and in analyzing some of the information 'out there' I realized that the key factor is the memory available vs. the high end of the range to be sieved (call it n).

There are algorithms that take essentially linear space (Dunten, Jones, and Sorenson) but sublinear time. These are fast if you're sieving from 1 to some small bound, say a billion. These have been largely replaced by the second category.

There are essentially-sqrt algorithms, of which the best is due to the late Atkin: amortized time 1/log log n, space n^(1/2 + eps). This is also useful when starting from 1, but can go considerably further -- limited mostly by processor time.

Galway's dissected sieve takes only n^(1/3) space, so it can be used to sieve a relatively small interval starting close to n. The price paid is time: the algorithm runs in linear time. (Galway also has a hybrid sieve conjectured to take only n^(1/4) space at the cost of another log log n factor in time. This could easily go to 10^30, but needs rather a lot of processor time as it requires large intervals to sieve, at least n^(1/2), to achieve even that time bound.)

Finally, there are the sieves and fake sieves that require almost no space. Sorenson’s pseudosquare sieve (based on Lukes-Patterson-Williams) is asymptotically as fast as Miller-Rabin, but the primes produced are proven. Further work on enumerating or bounding pseudosquares would be required to make this completely practical, but even at the current state of knowledge it's workable. It can't compete with Atkin-Bernstein or the others for small ranges, but it shines beyond a googol. Space requirement is O((log n)^2).

Bernstein's version of AKS is essentially quartic -- (log n)^(4+eps) -- so a theoretical possibility (not practical, ever) would be to test each number with this algorithm and a power detection algorithm. But since only a logarithmic fraction of numbers at a given size are expected to be prime, a cheap test (Miller-Rabin) that can guarantee compositeness in a large fraction of composites can be used. The cheap test is performed on all numbers, and the expensive AKS test is performed on only 1/log n numbers. This makes total performance:
(Cost of Miller-Rabin * 1) + (Cost of AKS * 1/log n) =
O((log n)^(2+eps)) + O((log n)^(4 + eps) / log n) =
O((log n)^(2+eps)) + O((log n)^(3 + eps)) =
O((log n)^(3 + eps))

So I was wondering: is there anything important I've left out? Or does anyone want to discuss the complexities I've used?

A. O. L. Atkin and D. J. Bernstein, “Prime sieves using binary quadratic forms”, Mathematics of Computation 73 (2004), pp. 1023–1030.
Daniel J. Bernstein , “Proving primality in essentially quartic expected time”, Mathematics of Computation 76 (2007), pp. 389–403.
B. Dunten, J. Jones, and J. Sorenson, “A space-efficient fast prime number sieve”, Information Processing Letters 59:2 (1996) , pp. 79–84.
William F. Galway, “Dissecting a sieve to cut its need for space”, Proceedings of the 4th International Symposium on Algorithmic Number Theory (2000), pp. 297–312.
William F. Galway, Analytic Computation of the Prime-Counting Function, Ph.D. thesis, University of Illinois.
Lukes, R. F.; Patterson, C. D.; and Williams, H. C. "Some Results on Pseudosquares." Math. Comput. 65 (1996), pp. 361–372 and S25-S27.
Jonathan P. Sorenson, “The Pseudosquares Prime Sieve”, Lecture Notes in Computer Science, Springer (2006), pp. 193–207.
CRGreathouse is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
sieving primes in arithmetic progressions maxal Software 18 2010-10-04 17:11
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
possible primes (real primes & products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 07:43.

Mon Apr 19 07:43:01 UTC 2021 up 11 days, 2:23, 0 users, load averages: 2.04, 2.04, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.