Generating primes

In mathematics, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.

For relatively small numbers, it is possible to just apply trial division to each successive odd number. Prime sieves are almost always faster.

Prime sieves

A prime sieve or prime number sieve is a fast type of algorithm for finding primes. There are many prime sieves, but the simple sieve of Eratosthenes, the faster but more complicated sieve of Atkinref|AB, and the various wheel sievesref|Pritchard are most common.

A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite numbers until only primes are left. This is the most efficient way to obtain a large range of primes; however, to find individual primes, direct primality tests are more efficient.

Large primes

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly-chosen range of odd numbers of the desired size is sieved against a number of relatively small odd primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard primality test such as the Miller-Rabin primality test for probable primes.

Alternatively, a number of techniques exist for efficiently generating provable primes. These include generating prime numbers "p" for which the prime factorization of "p" − 1 or "p" + 1 is known.

Complexity

The sieve of Eratosthenes is generally considered the easiest sieve to implement, but it is not the fastest. It can find all the primes up to "N" in time O("N"), while the sieve of Atkin and most wheel sieves run in sublinear time O("N"/log log "N"). The sieve of Atkin takes space "N"^1/2+o(1); Eratosthenes' sieve takes slightly less space O(N^1/2). Sorensonref|Sorenson shows an improvement to the wheel sieve that takes even less space at O("N"/((log "N")^Llog log "N") for any "L" > 1.

References

#A. Atkin, D.J. Bernstein, [http://cr.yp.to/papers/primesieves-19990826.pdf "Prime sieves using binary quadratic forms"] , "Mathematics of Computation" 73 (2004), pp. 1023–1030. [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf]
#Paul Pritchard, " [http://citeseer.ist.psu.edu/132206.html Improved Incremental Prime Number Sieves] ", "Algorithmic Number Theory Symposium" 1994, pp. 280–288.
#Jonathan P. Sorenson, " [http://citeseer.ist.psu.edu/14005.html Trading Time for Space in Prime Number Sieves] ", "Lecture Notes in Computer Science" Vol. 1423 (1998), pp. 179–195.