Corollary 2.5.2

Corollary 2.5.2 Suppose p and q are prime, and p =2q + 1. Suppose g Є Z*_p is not a

primitive element, and g ≠±1(mod p). Then (-g) is a primitive element.

This means that we have an efficient deterministic algorithm to find a primitive element

for when p and (p - 1)/2 are both prime.

It is not so easy to verify that elements are primitive if the factorization of p – 1 is

not known. For this reason, the designer of a cryptosystem will often construct p in such

a way that the factorization of p - 1 is known. For example, it is often desirable to

implement a cryptosystem in Z_p, where p =2q + 1 and p and q are both prime. One

reason why this might be done is that it ensures that the system will not be vulnerable

to a Pohlig-Hellman attack on the discrete logarithm problem. To find such a p, the

designer of the system will choose a random odd value q, and test both p and p =2q +1

for primality using one of the probablistic primality tests. If either of p or q is found

to be composite, then a new random value of q is chosen and the process is repeated.

As another example, several protocols are implemented in Z_p where p - 1 has a prime

divisor q of a specified size. A convenient realization of such a system would be to take

p =2qr + 1, where p, q and r are all primes. if q is to be a 160-bit prime and p is to be a

512-bit prime, then r will be a prime of approximately 352 bits. Here, the designer of the

system would begin by choosing random values q and r of the appropriate size, and then

define p =2qr + 1. The three integers p, q and r will all be tested for primality using a

probabilistic primality testing algorithm.

Corollary 2.5.1

Corollary 2.5.1 Suppose p and q are prime, and p =2q + 1. Suppose g Є Z*_p and

g ≠±1(mod p). Then g is a primitive element if and only if g^(p-1)/2 ≠ 1(mod p).

Proof. Observe that g^[(p-1)/q] ≠ g^2 (mod p), and g^2≡ 1(mod p)

if and only if g ≡≠1(mod p). Hence the result follows from the last Lemma.

In fact, If g ≠±1 (mod p) and g is not primitive, then g^(p-1)/2 ≡ 1(mod p). But then

we have Thus, by this Corollary (-g) must be primitive.

2.4.1 Finite Fields

2.4.1 Finite Fields

Definition 2.4.2 A finite field is a field F which contains a finite number elements. The order of F is the number of elements in F .

Theorem 2.4.3 (existence and uniqueness of finite fields)

1. If F is a finite field, then F contains p^m elements for some prie p and integer

m ≥ 1.

2. For every prime power order p^m, there is a unique (up to isomorphism) finite field of order p^m . This field is denoted F_p^m , or sometimes by GF(p^m).

Theorem 2.4.4 if F_q is a finite field of order q = p^m,p is a prime, then the characteristic of F_q is p. Moreover, F_q contains a copy of Z_p as a subfield. Hence F_q can be viewed as an extension field of Z_p of degree m.

Theorem 2.4.5 (subfields of a finite field) Let F_q be a finite field of order q = p^m. Then every subfield of F_q has order p^n, for some n that is a positive divisor of m. Conversely, if n is positive divisor of m, then there is exactly one subfield of F_q of order p^n; an element a Є F_q is in the subfield F_p^n if and only if a^p_n = a.

Definition 2.4.3 The non-zero elements of F_q from a group under multiplication called the multiplicative group of F_q, denoted F*_q .

Theorem 2.4.6 F*_q is a cyclic group of order q - 1. Hence a^q = a for all a ЄF_q .

Proposition 2.4.1 The order of any a F*_q devides q - 1.

Proof. Fo r a^(q-1) = 1 let d be the order of a, i.e., the smallest positive power which gives 1. If d

did not divide q - 1, we could find a smaller positive number r- namely, the remainder

when

q - 1=bd + r, where 1≤ r

is divided by d- such that

a^r. a^(bd) = a^(q-1) =1.

But this contradicts the minimality of d. This concludes the proof.

Definition 2.4.4 A generator of the cyclic group F*_q is called a primitive element or

generator of F_q .

Theorem 2.4.7 If a, b Є F_q, a finite field of characteristic p, then

(a + b)^(p^t) = a^(p^t) + b^(p^t) for all t ≥ 0.