In computational number theory, 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.
Prime sieves[edit | edit source]
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 AtkinTemplate:Ref, and the various wheel sievesTemplate:Ref 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[edit | edit source]
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.
Complexity[edit | edit source]
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 N1/2+o(1); Eratosthenes' sieve takes slightly less space O(N1/2). SorensonTemplate:Ref 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[edit | edit source]
- Template:NoteA. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Mathematics of Computation 73 (2004), pp. 1023–1030. 
- Template:NotePaul Pritchard, "Improved Incremental Prime Number Sieves", Algorithmic Number Theory Symposium 1994, pp. 280–288.
- Template:NoteJonathan P. Sorenson, "Trading Time for Space in Prime Number Sieves", Lecture Notes in Computer Science Vol. 1423 (1998), pp. 179–195.