ANSI X9.80:2005 pdf download.Prime Number Generation, Primality Testing, and Primality Certificates.
The algorithms approved by this standard include the following:
1. Testing of Randomly Ctosen 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
1 B. 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
— Krailchik-Lehmer, Section 5,2,4.1.3
— ECPP (Elliptic Curve Pnmality Proof), Section 5.2.4.2
2. Methods for Direct Construction of Prime Numbers
— Maurer’s Algorithm. Section 5.3.1
— Shawe-Taytor’s Algorithm, Section 5.3.2
A method for generating random primes over an interval Ia. bJ that gives an equal probability of selecting each prime, Is simply to generate a random integer in [a. bi, then test it for pnmal.ty. 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 pmimality 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 ii 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 2u00.
This standard allows three different probabilistic procedures to be used. The first is to use at least 50 rounds of the Miller-Rabin algorithm (see Section 5.2.3.1). The second Is using multiple rounds of the Miller-Rabin algorithm followed by a single round of the Lucas algorithm (see Section 5.2.3.2). Composite integers that fool multiple rounds of Miller-Rabin are knowii to exist. However, there Is no known composite integer that passes even a sin9le Miller-Rabin test to the base 2 followed by a single Lucas test. This combination was suggested by Pomerance. Selfridge and Wagstaff [11]. While heuristics suggest that such integers do exist, they must be exceedingly rare, and no example is known. Indeed, a prize offered in Ill) for such a composite remains unclaimed. In previous X9 standards, only the use of multiple rounds of Miller-Rabin was specified as an acceptable method. However, including a single follow-up round of Lucas lowers the probability of error dramatically. The number of rounds required for Miller-Rabin used in conjunction with Lucas is given in Table 2 (Section 7). This second method is expected to have better performance than the first, but Is more complex and takes more code.
The third probabilistic procedure is due to Grantham 161. It is sightly more complicated to code than Miller-Rabin and Lucas. Each iteration takes about 3 times as long, but it has the advantage that the probability of failure for each iteration of Frobenius-Grantham (see Section 5.2.3.3) is considerably lower than a single iteration of MillerRabin. The number of rounds required for Frobenius-Graritham is given in Table 3 (Section 7). At the time of publication of this standard, unlike for Miller-Rabin. there is no known mathematical method for constructing integers that achieve the worst-case probability of error for this test.
Damgaard, Landrock. and Pomerance (5J provide upper bounds on the probability of a failure of multiple rounds of Miller-Rabin based upon the size of the number being tested, assuming that the candidate was randomly chosen. These results are given in Table 2. Similar results have yet to be computed for the Frobenius-Gantham method. However, based upon the probability of a single iteration failing (which can be derived from [6J). along with the upper bound per iteration probability of failure, a aude upper bound table for the number of required rounds of Frobenius-Grantham can be constructed. This is provided in Table 3. It is not a sharp estimate in the sense that the actual probabilities of failure are much lower than given by the table. When the results of [5) are extended to the Frobenius-Grantham method, Table 3 can be revised.
