Prime number generation
This section considers algorithms for the generation of prime numbers for cryptographic purposes. Four algorithms are presented: Algorithm 4.44 for generating probable primes (see Definition 4.5), Algorithm 4.53 for generating strong primes (see Definition 4.52), Algorithm 4.56 for generating probable prunes p and q suitable for use in the Digital Signature Algorithm (DS A), and Algorithm 4.62 for generating provable primes (see Definition 4.34).
4.43 Note (prime generation vs. primality testing) Prime number generation differs from primality testing as described in §4.2 and §4.3, but may and typically does involve the latter. The former allows the construction of candidates of a fixed form which may lead to more efficient testing than possible for random candidates.
Random search for probable primes
By the prime number theorem (Fact 2.95), the proportion of (positive) integers < x that are prune is approximately 1 / In x. Since half of all integers < x are even, the proportion of odd integers < x that are prime is approximately 2/ In ж. For instance, the proportion of all odd integers < 2^{512} that are prime is approximately 2/(512 • ln(2)) « 1/177. This suggests that a reasonable strategy for selecting a random A:bit (probable) prime is to repeatedly pick random Аbit odd integers n until one is found that is declared to be “prime” by MILLERRABIN(n.f) (Algorithm 4.24) for an appropriate value of the security parameter t (discussed below).
If a random Abit odd integer n is divisible by a small prime, it is less computationally expensive to rule out the candidate n by trial division than by using the MillerRabin test. Since the probability that a random integer n has a small prune divisor is relatively large, before applying the MillerRabin test, the candidate n should be tested for small divisors below a predetennined bound B. This can be done by dividing n by all the primes below B, or by computing greatest common divisors of n and (precomputed) products of several of the primes < B. The proportion of candidate odd integers n not ruled out by this trial division is Пз<_{Р}<«(1 ~ p) which, by Mertens’s theorem, is approximately 1.12/ In В (here p ranges over prime values). For example, if В = 256, then only 20% of candidate odd integers n pass the trial division stage, i.e., 80% are discarded before the more costly Miller Rabin test is performed.
4.44 Algorithm Random search for a prime using the MillerRabin test RANDOMSEARCH(A,f)
INPUT: an integer k, and a security parameter t (cf. Note 4.49).
OUTPUT: a random Л bit probable prime.
 1. Generate an odd /. bit integer n at random.
 2. Use trial division to determine whether n is divisible by any odd prune < В (see Note 4.45 for guidance on selecting B). If it is then go to step 1.
 3. If MILLERRABIN(n,f) (Algorithm 4.24) outputs “prime” then return(n). Otherwise, go to step 1.
 4.45 Note (optimal trial division bound B) Let E denote the time for a full kbit modular exponentiation, and let D denote the time required for ruling out one small prime as divisor of a Abit integer. (The values E and D depend on the particular implementation of long integer arithmetic.) Then the trial division bound В that minimizes the expected running time of Algorithm 4.44 for generating a Abit prune is roughly В = E/D. A more accurate estimate of the optimum choice for В can be obtained experimentally. The odd primes up to В can be precomputed and stored in a table. If memory is scarce, a value of В that is smaller than the optimum value may be used.
Since the MillerRabin test does not provide a mathematical proof that a number is indeed prune, the number n returned by Algorithm 4.44 is a probable prime (Definition 4.5). It is important, therefore, to have an estimate of the probability that n is in fact composite.
 4.46 Definition The probability that RANDOMSEARCH(A,i) (Algorithm 4.44) returns a composite number is denoted by prj.
 4.47 Note (remarks on estimating pk.i) It is tempting to conclude directly from Fact 4.25 that Pkj < (!)*• This reasoning is flawed (although typically the conclusion will be correct in practice) since it does not take into account the distribution of the prunes. (For example, if all candidates n were chosen from a set S of composite numbers, the probability of error is
 1.) The following discussion elaborates on this point. Let X represent the event that n is composite, and let Y_{t} denote the event than MILLERRABIN(n.f) declares n to be prime. Then Fact 4.25 states that P(Y_{t}X) < ()‘. What is relevant, however, to the estimation of Pkj is the quantity P(XY_{t}). Suppose that candidates n are drawn uniformly and randomly from a set 5 of odd numbers, and suppose p is the probability that n is prune (this depends on the candidate set S). Assume also that ()<;;< 1. Then by Bayes’ theorem (Fact 2.10):
J
since P(Y_{t}) > p. Thus the probability P(XY,) may be considerably larger than ()* if p is small. However, the errorprobability of MillerRabin is usually far smaller than ()^{f} (see Remark 4.26). Using better estimates for P{Y,X) and estimates on the number of kbit prune numbers, it has been shown that pk,t is, in fact, smaller than ()' for all sufficiently large к. A more concrete result is the following: if candidates n are chosen at random from the set of odd numbers in the interval [3, ж], then P(XY_{t}) < ()^{f} for all x > 10^{GO}.
Further refinements for P(Y_{t}X) allow the following explicit upper bounds on pk.t for various values of к and t. ^{[1]}
4.48 Fact (some upper bounds on pkj i>i Algorithm 4.44)
For example, if к = 512 and t = 6, then Fact 4.48(ii) gives ръ1,а < ()^{88} In other words, the probability that RANDOMSEARCH(512,6) returns a 512bit composite integer is less than (I)^{88}. Using more advanced techniques, the upper bounds on pk.t given by Fact 4.48 have been improved. These upper bounds arise from complicated formulae which are not given here. Table 4.3 lists some improved upper bounds on pk.t for some sample values of к and t. As an example, the probability that RANDOMSEARCH(500,6) returns a composite number is < ()^{92}. Notice that the values of pkj implied by the table are considerably smaller than ()^{4} = ()^{2t}.
к 
t 

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 

100 
5 
14 
20 
25 
29 
33 
36 
39 
41 
44 
150 
8 
20 
28 
34 
39 
43 
47 
51 
54 
57 
200 
11 
25 
34 
41 
47 
52 
57 
61 
65 
69 
250 
14 
29 
39 
47 
54 
60 
65 
70 
75 
79 
300 
19 
33 
44 
53 
60 
67 
73 
78 
83 
88 
350 
28 
38 
48 
58 
66 
73 
80 
86 
91 
97 
400 
37 
46 
55 
63 
72 
80 
87 
93 
99 
105 
450 
46 
54 
62 
70 
78 
85 
93 
100 
106 
112 
500 
56 
63 
70 
78 
85 
92 
99 
106 
113 
119 
550 
65 
72 
79 
86 
93 
100 
107 
113 
119 
126 
600 
75 
82 
88 
95 
102 
108 
115 
121 
127 
133 
Table 4.3: Upper bounds on pk.t for sample values of к and t. An entry j corresponding to к and t impliesp_{M} < (I)^{J}.
4.49 Note (controlling the error probability) In practice, one is usually willing to tolerate an error probability of ( )^{80} when using Algorithm 4.44 to generate probable primes. For sample values of k, Table 4.4 lists the smallest value of t that can be derived from Fact 4.48 for which prj < (I)^{80}. For example, when generating 1000bit probable primes, Miller Rabin with t = 3 repetitions suffices. Algorithm 4.44 rules out most candidates n either by trial division (in step 2) or by performing just one iteration of the MillerRabin test (in step 3). For this reason, the only effect of selecting a larger security parameter t on the running time of the algorithm will likely be to increase the time required in the final stage when the (probable) prime is chosen.
к 
t 
100 
27 
150 
18 
200 
15 
250 
12 
300 
9 
350 
8 
400 
7 
450 
G 
к 
t 
500 
6 
550 
5 
GOO 
5 
G50 
4 
700 
4 
750 
4 
800 
4 
850 
3 
к 
t 
900 
3 
950 
3 
1000 
3 
1050 
3 
1100 
3 
1150 
3 
1200 
3 
1250 
3 
к 
t 
1300 
2 
1350 
2 
1400 
2 
1450 
2 
1500 
2 
1550 
2 
1G00 
2 
1650 
2 
к 
t 
1700 
2 
1750 
2 
1800 
2 
1850 
2 
1900 
2 
1950 
2 
2000 
2 
2050 
2 
Table 4.4: For sample k. the smallest t from Fact 4.48 is given for which pk.t < ( )^{80} •
 4.50 Remark (MillerRabin test with base a = 2) The MillerRabin test involves exponentiating the base a; this may be performed using the repeated squareandmultiply algorithm (Algorithm 2.143). If о = 2, then multiplication by a is a simple procedure relative to multiplying by a in general. One optimization of Algorithm 4.44 is, therefore, to fix the base a = 2 when first performing the MillerRabin test in step 3. Since most composite numbers will fail the MillerRabin test with base a = 2, this modification will lower the expected running tune of Algorithm 4.44.
 4.51 Note {incremental search)
 (i) An alternative technique to generating candidates n at random in step 1 of Algorithm 4.44 is to first select a random fcbit odd number n_{0}, and then test the s numbers n = no, no + 2, no + 4,... , no + 2(s — 1) for primality. If all these s candidates are found to be composite, the algorithm is said to have failed. If s = c • In 2^{k} where c is a constant, the probability qk,t,_{s} that this incremental search variant of Algorithm 4.44 returns a composite number has been shown to be less than 5k^{3}2^{_v}^ for some constant Table 4.5 gives some explicit bounds on this error probability for к = 500 and t < 10. Under reasonable numbertheoretic assumptions, the probability of the algorithm failing has been shown to be less than 2e^{2c} for large к (here, e « 2.71828).
 (ii) Incremental search has the advantage that fewer random bits are required. Furthermore, the trial division by small primes in step 2 of Algorithm 4.44 can be accomplished very efficiently as follows. First the values R[/> = n_{0} mod p are computed for each odd prime p < B. Each tune 2 is added to the current candidate, the values in the table R are updated as Rp]^(Rp] + 2) mod p. The candidate passes the trial division stage if and only if none of the Rp] values equal 0.
 (iii) If В is large, an alternative method for doing the trial division is to initialize a table S[i]<0 for 0 < i < (s  1); the entry S[i] corresponds to the candidate no + 2i. For each odd prime p < B,n_{0} mod p is computed. Let j be the smallest index for
c 
t 

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 

1 
17 
37 
51 
63 
72 
81 
89 
96 
103 
110 
5 
13 
32 
40 
58 
68 
77 
85 
92 
99 
105 
10 
11 
30 
44 
56 
66 
75 
83 
90 
97 
103 
Table 4.5: Upper bounds on the error probability of incremental search (Note 4.51) for к = 500 and sample values of c and t. An entry j conesponding to c and t implies qeoo t s < (i)^{J}, where s = c ln2^{500}.
which (no + 2j) = 0 (mod p). Then S[j] and each p^{th} entry after it are set to 1. A candidate n_{0} + 2i then passes the trial division stage if and only if S[i] = 0. Note that the estimate for the optimal trial division bound В given in Note 4.45 does not apply here (nor in (ii)) since the cost of division is amortized over all candidates.
 [1] The estimates of presented in the remainder of this subsection were derived for the situation where Algorithm 4.44 does not use trial division by small primes to rule out some candidates n. Since trial division neverrules out a prime, it can only give a better chance of rejecting composites. Thus the error probability p/>( mightactually be even smaller than the estimates given here.