Generating primes
Encyclopedia
In computational number theory
, a variety of algorithm
s make it possible to generate prime number
s efficiently. These are used in various applications, for example hashing
, public-key cryptography
, and search of prime factor
s 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.
, the faster but more complicated sieve of Atkin
, and the various wheel sieves
are most common.
A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite number
s (which it directly generates) 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 test
s are more efficient.
for probable prime
s.
Alternatively, a number of techniques exist for efficiently generating provable prime
s. These include generating prime numbers p for which the prime factorization of p − 1 or p + 1 is known.
(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); segmented Eratosthenes' sieve takes slightly less space than O(N1/2). 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.
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
, a variety of algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s make it possible to generate prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s efficiently. These are used in various applications, for example hashing
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
, public-key cryptography
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
, and search of prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s in large numbers.
For relatively small numbers, it is possible to just apply trial division
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
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 EratosthenesSieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
, the faster but more complicated sieve of Atkin
Sieve of Atkin
In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. ...
, and the various wheel sieves
Wheel factorization
Wheel factorization is a graphical method for manually performing a preliminary to the Sieve of Eratosthenes that separates prime numbers from composites. Start by writing the natural numbers around circles as shown below. Prime numbers in the innermost circle have their multiples in similar...
are most common.
A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
s (which it directly generates) 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 test
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
s 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 testMiller-Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithmwhich determines whether a given number is prime,...
for probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
s.
Alternatively, a number of techniques exist for efficiently generating provable prime
Provable prime
In number theory, a provable prime is an integer that is calculated to be prime using a primality-proving algorithm. Contrast with probable prime, which is likely to be prime, based on the output of a probabilistic algorithm. There are algorithms that prove the primality of an integer. AKS...
s. 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 OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(N), while the sieve of Atkin
Sieve of Atkin
In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. ...
and most wheel sieves run in sublinear time O(N/log log N). The sieve of Atkin takes space N1/2+o(1); segmented Eratosthenes' sieve takes slightly less space than O(N1/2). 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.