Generating primes

From Wikipedia, the free encyclopedia

It has been suggested that prime sieve be merged into this article or section. (Discuss)

A variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, from hashing to public-key cryptography.

For small numbers, it suffices simply to apply trial division to each successive odd number.

For slightly larger numbers, or where efficiency is important, the Sieve of Eratosthenes or the faster and more complex Sieve of Atkin can efficiently generate all primes below a given number.

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.

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

This cryptography-related article is a stub. You can help Wikipedia by expanding it.