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. For relatively small numbers, it is possible to just apply trial division to each successive odd number. Prime sieves are almost always faster. Prime sieving is the fastest known way to deterministically enumerate the primes. There are some known formulas that can calculate the next prime but there is no known way to express the next prime in terms of the previous primes. Also, there is no effective known general manipulation and/or extension of some mathematical expression (even such including later primes) that deterministically calculates the next prime.
Prime sieves A prime sieve or prime number sieve is a fast type of algorithm for finding primes. There are many prime sieves. The simple sieve of Eratosthenes (250s BCE), the sieve of Sundaram (1934), the still faster but more complicated sieve of Atkin (2003), sieve of Pritchard (1979), and 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 numbers (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 tests are more efficient. Furthermore, based on the sieve formalisms, some integer sequences (sequence A240673 in the OEIS) are constructed which also could be used for generating primes in certain intervals. Historically some prime sieves were realised or partly realised in hardware, including the stencils used by Anton Felkel, Carl Hindenburg and D. N. Lehmer as aids to manual computation; and the electromechanical machines, and one later electronic machine, known as the Lehmer sieves by D. H. Lehmer (on at least one occasion with D. N. Lehmer).
Large primes Cryptography requires the use of very large primes: for example, with the RSA cryptosystem two primes of at least 1,024 bits (i.e. at least 21023) are recommended. To generate these primes, the mainstream method is to generate random numbers in a target range and test them for primality using fast probabilistic methods: a short round of sieving (sieve of Eratosthenes or trial division) followed by Baillie–PSW primality test or the Miller–Rabin primality test; a probable prime with a chance of 2-112 of being composite is considered plenty for the 2,048-bit case. Even if a composite number is chosen, it will likely be quickly discovered by causing failed operations, except when a Carmichael number happens to be chosen in the case of RSA. A less common choice is to use provable primes, which can be generated based on variants of Pocklington primality test, especially Maurer's algorithm. Both the provable and probable primality tests rely on modular exponentiation. In addition with RSA, so-called "strong primes" with both p-1 and p+1 having a large prime factor is preferred, as this is expected to slow down factoring attempts using the Polard's p-1 and Williams' p+1 algorithms. Such a choice has little effect against elliptic-curve factoring methods, however. Integers of special forms, such as Mersenne primes or Fermat primes, can be efficiently tested for primality if the prime factorization of p − 1 or p + 1 is known.
… excerpt ends here. Continue reading the full article.
