# 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 < 2512 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 MILLER-RABIN(n.f) (Algorithm 4.24) for an appropriate value of the security parameter t (discussed below).

If a random A-bit 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 Miller-Rabin test. Since the probability that a random integer n has a small prune divisor is relatively large, before applying the Miller-Rabin test, the candidate n should be tested for small divisors below a pre-detennined bound B. This can be done by dividing n by all the primes below B, or by computing greatest common divisors of n and (pre-computed) 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 Miller-Rabin test RANDOM-SEARCH(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 MILLER-RABIN(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 k-bit modular exponentiation, and let D denote the time required for ruling out one small prime as divisor of a A-bit 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 A-bit 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 Miller-Rabin 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 RANDOM-SEARCH(A,i) (Algorithm 4.44) returns a composite number is denoted by pr-j.
• 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 Yt denote the event than MILLER-RABIN(n.f) declares n to be prime. Then Fact 4.25 states that P(YtX) < (|)‘. What is relevant, however, to the estimation of Pkj is the quantity P(XYt). 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(Yt) > p. Thus the probability P(XY,) may be considerably larger than (|)* if p is small. However, the error-probability of Miller-Rabin is usually far smaller than (|)f (see Remark 4.26). Using better estimates for P{Y,X) and estimates on the number of k-bit 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(XYt) < (|)f for all x > 10GO.

Further refinements for P(YtX) 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 RANDOM-SEARCH(512,6) returns a 512-bit 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 RANDOM-SEARCH(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 impliespM < (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 1000-bit 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 Miller-Rabin 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 (Miller-Rabin test with base a = 2) The Miller-Rabin test involves exponentiating the base a; this may be performed using the repeated square-and-multiply 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 Miller-Rabin test in step 3. Since most composite numbers will fail the Miller-Rabin 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 fc-bit odd number n0, 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 2k 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 5k32_v^ for some constant Table 4.5 gives some explicit bounds on this error probability for к = 500 and t < 10. Under reasonable number-theoretic 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[/> = n0 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,n0 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 ln2500.

which (no + 2j) = 0 (mod p). Then S[j] and each pth entry after it are set to 1. A candidate n0 + 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.