 recognize that when the minimum polynomial ma(z) of a over GF(q) has degree d, then a, a9, Qq2 aqd-1 are its distinct roots, -Trg(a) is the coefficient of zd-1 in ma(z), and the trace is therefore in GF(q). However, when ma(z) has degree k, k < d (k must divide d), then the roots of ma(z) appear dlk times in (5.121) and Tra(a) is (d/k)Trq(a). Once a primitive element a has been specified by choosing its minimum polynomial ma(z) of degree d over GF(q), then the trace of any non-zero element Ok in GF(q) can be evaluated directly. (5.126) The substitution of zi for Z in the trace polynomial allows the evaluation of the trace of aj by substitution of a, and the reduction of the resulting poly- nomial mod ma(z) eliminates terms which will be zero upon evaluation at a. The result on the right side of (5.126) is an element of S (see (5.103)), while Property T-2 implies that the quantity on the left must be in GF(q). Since the elements of Sd corresponding to GF(q) elements are in fact those same elements, i.e., only X0 in (5.104) is non-zero in this case, the substitu- tion of Z = a on the right side of (5.126) is not necessary. Example 5.8. Let a be a root of the primitive polynomial z5 + z2 + 1. The root a and its conjugates (other roots of the same primitive polynomial), namely a2, a4, a8, and 16, are elements of GF(32). Other elements of GF(32) can also be grouped into root sets. The powers on a corresponding to a root set must be relatively prime to the order of a to insure that the corresponding polynomial is primitive. In this case primitivity is guarantee for all degree 5 irreducible polynomials because the order of a, namely 31, Galois Field Connections Table 5.9 Cyclotomic cosets and associated trace function values when a is a root of 25 + z2 + 1 over GF(2). Cyclotomic coset elements X Tr2(ax) 1,2,4,8,16 3, 6, 12, 24, 17 5, 10, 20, 9, 18 7, 14, 28, 25, 19 11, 22, 13, 26, 21 15, 30, 29, 27, 23 is prime. Each set of root powers is called a cyclotomic coset (see Appendix 5A.8). Property T-2 indicates that all th