# 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 > 21G0. This suggests the following algorithm for selecting appropriate parameters (p. a).

4.84 Algorithm Selecting a k-b'ti primep 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 = 2Rq, 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 2q. 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).