ANSI X9.80-2005 pdf download Prime Number Generation, Primality Testing, and Primality Certificates
5 Prime Generation Methods
5.1 General Discussion
This section discusses prime generation by a first party; i.e. generation of primes by the user of said primes. Prime numbers may be generated by a variety of methods.
The methods are categorized into two groups. The first group generates candidate integers at random and then tests them for primality using either a probabilistic or deterministic algorithm. These methods are discussed in Section 5.2.
The second set of methods actually constructs integers from smaller integers in such a way that the constructed integer is guaranteed to be prime. These methods are discussed in Section 5.3. Section 5.4 discusses how to generate primes subject to side conditions. A typical side condition might be that a prime p must have p–1 divisible by a large prime factor. ANSI X9.31 requires, for example, that p–1 must have a prime factor of at least 100 bits.
The algorithms approved by this standard include the following:
1. Testing of Randomly Chosen Integers
1A. Probabilistic Methods for Testing Integers
— Miller-Rabin, Section 5.2.3.1
— Lucas, Section 5.2.3.2
— Frobenius-Grantham, Section 5.2.3.3
1B. Deterministic Methods for Testing Integers
— Trial division (for sufficiently small primes, e.g. up to 10 decimal digits), Section 5.2.4.1.1
— The Selfridge extensions to PPL (Proth, Pocklington, & Lehmer), Section 5.2.4.1.2
— Kraitchik-Lehmer, Section 5.2.4.1.3
— ECPP (Elliptic Curve Primality Proof), Section 5.2.4.2
2. Methods for Direct Construction of Prime Numbers
— Maurer’s Algorithm, Section 5.3.1
— Shawe-Taylor’s Algorithm, Section 5.3.2
A method for generating random primes over an interval [a, b] that gives an equal probability of selecting each prime, is simply to generate a random integer in [a, b], then test it for primality. If it is not prime, then continue generating random integers and testing them until a prime is found. This method is much too slow to be of practical use, but it is allowed by this standard. Instead, a method is given in Section 5.2.1 that selects primes almost uniformly at random, but is significantly faster than the method suggested above.
Candidate primes can be tested for primality using either a probabilistic or a deterministic algorithm. The difference between these two is that a deterministic algorithm takes a candidate integer and proves whether the candidate is prime, whereas a probabilistic algorithm only declares that the candidate is probably prime. For each invocation of the algorithm, there is a small probability that it will erroneously declare a composite integer to be prime. For this reason, probabilistic algorithms are run more than once in order to ensure that the probability of error is sufficiently small. This standard defines that probability to be 2 –100 .