 Constructive techniques for provable primes

Maurer’s algorithm (Algorithm 4.62) generates random provable primes that are almost uniformly distributed over the set of all prunes of a specified size. The expected time for generating a prune is only slightly greater than that for generating a probable prime of equal size using Algorithm 4.44 with security parameter t = 1. (In practice, one may wish to choose t > 1 in Algorithm 4.44; cf. Note 4.49.)

The main idea behind Algorithm 4.62 is Fact 4.59, which is a slight modification of Pocklington’s theorem (Fact 4.40) and Fact 4.41.

• 4.59 Fact Let n > 3 be an odd integer, and suppose that n = 1 + 2Rq where q is an odd prime. Suppose further that q > R.
• (i) If there exists an integer a satisfying a”"1 = 1 (mod n) and gcd(a2i? - l.n) = 1, then n is prime.
• (ii) If n is prime, the probability that a randomly selected base a, < a 1, satisfies an-i = 1 (mod n) andgcd(a2fi — l.n) = 1 is (1 — 1 /q).

Algorithm 4.62 recursively generates an odd prune q, and then chooses random integers R, R < q, until n = 2Rq + 1 can be proven prune using Fact 4.59(i) for some base a. By Fact 4.59(ii) the proportion of such bases is 1 - l/q for prime n. On the other hand, if n is composite, then most bases a will fail to satisfy the condition a"-1 = 1 (mod n).

• 4.60 Note (description of constants c and m in Algorithm 4.62)
• (i) The optimal value of the constant c defining the trial division bound В = ck2 in step 2 depends on the implementation of long-integer arithmetic, and is best determined experimentally (cf. Note 4.45).
• (ii) The constant m = 20 ensures that I is at least 20 bits long and hence the interval from which R is selected, namely [I + 1,2/], is sufficiently large (for the values of к of practical interest) that it most likely contains at least one value R for which n = 2Rq + 1 is prime.
• 4.61 Note (relative size r of q with respect to n in Algorithm 4.62) The relative size r of q with respect to n is defined to be r = lg qj lg n. In order to assure that the generated prune n is chosen randomly with essentially uniform distribution from the set of all Л -bit primes, the size of the prime factor q of n - 1 must be chosen according to the probability distribution of the largest prune factor of a randomly selected Л-bit integer. Since q must be greater than R in order for Fact 4.59 to apply, the relative size ?• of q is restricted to being in the interval [|, 1]. It can be deduced from Fact 3.7(i) that the cumulative probability distribution of the relative size r of the largest prune factor of a large random integer, given that r is at least

is (1 + lgr) for < r < 1. In step 4 of Algorithm 4.62, the relative size r is generated according to this distribution by selecting a random number s e [0,1] and then setting r = 2s-1. If к < 2m then r is chosen to be the smallest permissible value, namely Л, in order to ensure that the interval from which R is selected is sufficiently large (cf. Note 4.60(ii)).

4.62 Algorithm Maurer’s algorithm for generating provable primes

PROVABLE J?RIME(/e)

INPUT: a positive integer k.

OUTPUT: a A--bit prime number n.

1. (If к is small, then test random integers by trial division. A table of small primes may be precomputed for this purpose.)

If к < 20 then repeatedly do the following:

• 1.1 Select a random fc-bit odd integer n.
• 1.2 Use trial division by all primes < ^/n to determine whether n is prime.
• 1.3 If n is prime then retum(n).
• 2. Set c<-0.1 and m<-20 (see Note 4.60).
• 3. (Trial division bound) Set Bj—c ■ к2 (see Note 4.60).
• 4. (Generate r, the size of q relative to n — see Note 4.61) If к > 2m then repeatedly do the following: select a random number s in the interval [0,1], set r«-2s_1, until (k - rk) > m. Otherwise (i.e. к < 2m), set r<-0.5.
• 5. Compute q^-PROVABLEJPRIME( |r • k + 1).
• 6. Set I<—[2k~   {{(iii) Step 4 requires the use of real number arithmetic when computing 26~. To avoidthese computations, one can precompute and store a list of such values for a selectionof random numbers s e [0,1].}} /(2q).
• 7. success<-0.
• 8. While (success = 0) do the following:
• 8.1 (select a candidate integer n) Select a random integer R in the interval [I + 1,21} and set n<-2Rq + 1.
• 8.2 Use trial division to determine whether n is divisible by any prime number < B. If it is not then do the following:

Select a random integer a in the interval [2, n - 2].

Compute bin—1 mod n.

If b = 1 then do the following:

Compute br—a2R mod n and dr— gcd(6 — 1, n).

If d = 1 then success's—!.

9. Retum(n).

to its recursive nature. Provable primes are preferable to probable primes in the sense that the former have zero error probability. In any cryptographic application, however, there is always a non-zero error probability of some catastrophic failure, such as the adversary guessing a secret key or hardware failure. Since the error probability of probable primes can be efficiently brought down to acceptably low levels (see Note 4.49 but note the dependence on t), there appears to be no reason for mandating the use of provable prunes over probable primes.

•  4.63 Note (improvements to Algorithm 4.62)
•  A speedup can be achieved by using Fact 4.42 instead of Fact 4.59(i) for provingn = 2 Rq + 1 prime in step 8.2 of Maurer’s algorithm — Fact 4.42 only requires thatq be greater than ^/n.
•  (ii) If a candidate n passes the trial division (in step 8.2), then a Miller-Rabin test (Algorithm 4.24) with the single base a = 2 should be performed on n; only if n passesthis test should the attempt to prove its primality (the remainder of step 8.2) be undertaken. This leads to a faster implementation due to the efficiency of the Miller-Rabintest with a single base a = 2 (cf. Remark 4.50).
•  (iii) Step 4 requires the use of real number arithmetic when computing 26~{{ A speedup can be achieved by using Fact 4.42 instead of Fact 4.59(i) for provingn = 2 Rq + 1 prime in step 8.2 of Maurer’s algorithm — Fact 4.42 only requires thatq be greater than ^/n.
•  4.64 Note (provable primes vs. probable primes) Probable prunes are advantageous over prov