# Selecting a prime p and generator of Z*p

In cryptographic applications for which a generator of Z* is required, one usually has the flexibility of selecting the prime *p.* To guard against the Pohlig-Hellman algorithm for computing discrete logarithms (Algorithm 3.63), a security requirement is that *p—* 1 should contain a “large” prime factor *q.* In this context, “large” means that the quantity *^/q* represents an infeasible amount of computation; for example, *q* > 2^{1G0}. This suggests the following algorithm for selecting appropriate parameters *(p.* a).

4.84 Algorithm Selecting a *k-b'ti* prime*p* and a generator» of *Щ,*

INPUT: the required bitlength *к* of the prime and a security parameter *t.*

OUTPUT: a А-bit prime *p* such that *p —* 1 has a prime factor > *t,* and a generator a of Z*.

- 1. Repeat the following:
- 1.1 Select a random fc-bit prime
*p*(for example, using Algorithm 4.44). - 1.2 Factor
*p -*1.

Until *p* — 1 has a prime factor > *t.*

- 2. Use Algorithm 4.80 with
*G =*Z* and*n = p*- 1 to find a generator*a*of Z*. - 3.
**Return(p,a).**

Algorithm 4.84 is relatively inefficient as it requires the use of an integer factorization algorithm in step 1.2. An alternative approach is to generate the prime *p* by first choosing a large prime *q* and then selecting relatively small integers *R* at random until *p = 2Rq + **1 *is prime. Since *p* — 1 = 2*Rq,* the factorization of *p -* 1 can be obtained by factoring *R.* A particularly convenient situation occurs by imposing the condition *R* = 1. In this case the factorization of *p* - 1 is simply 2*q.* Furthermore, since *ф(р* - 1) = *ф(2q)* = *(2) (q) = q —* 1, the probability that a randomly selected element о e Z* is a generator is

*к*3.

4.85 Definition A *safe prime p* is a prime of the form *p = 2q* + 1 where *q* is prime.

Algorithm 4.86 generates a safe (probable) prime *p* and a generator of Z*.

4.86 Algorithm Selecting a A>bit safe prime *p* and a generator a of Z*

INPUT: the required bitlength *к* of the prime.

OUTPUT: а А-bit safe prime *p* and a generator q of Z*.

- 1. Do the following:
- 1.1 Select a random
*(k -*l)-bit prime*q*(for example, using Algorithm 4.44). - 1.2 Compute
*p<^2q*+ 1, and test whether*p*is prime (for example, using trial division by small primes and Algorithm 4.24).

Until *p* is prime.

- 2. Use Algorithm 4.80 to find a generator
*a*of Z*. - 3. Return(p,a).