Generating Primes - Large Primes

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.

Read more about this topic:  Generating Primes

Famous quotes containing the word large:

    We can see nothing whatever of the soul unless it is visible in the expression of the countenance; one might call the faces at a large assembly of people a history of the human soul written in a kind of Chinese ideograms.
    —G.C. (Georg Christoph)