 of this equation by the inverse of x9' in GF(q) gives xq'-q = (5A.57) which implies that the order e of x divides qj i Hence, eqqq 1). Since eqd - 1, it follows that gcd(e,q) = 1, el(qj-1 and, therefore, by Theorem 5A.11, d VI j - i. Since j and i are both non-neg- ative integers, X, xx, , are all distinct. Because a polynomial over a field can have no more roots than its degree, these elements are all the roots of mx(z). We now have an alternative algorithm for determining the roots of m,(z) over GF(q) whenever the arithmetic for any extension field of GF(q), con- taining y, is specified. q-Conjugate Algorithm for Determining my(z) over GF(q). (a) Compute y, until an integer d is reach for which yas==y. = (b) Form the polynomial (5A.58) (c) Evaluate the coefficients of m,(z) in (b) using the arithmetic specified for the field. We shall again provide an example from GF(16). This time, for the sake of variety, we shall use the notation of the addition and multiplication tables of Figure 5A.1. Example 5A.14. As a check, let us again consider the element h of GF (16), and try to find mh(z) over GF(2) using the q-conjugate method. (a) h20 = h Pseudonoise Generators (b) mh(z) h)(z-h2(z-h4(z- mh(z) = h)(z - 9)(z - p)(z - m) (z4-(c+f)z3+(k+q+fc)z2-(ck = + fg)z gk = z4 +z3+1(overGF(2)) (c) This is a check on the previous computation. Using Theorem 5A.12, the entire collection of non-zero elements of GF(qd) can be separated into disjoint sets, each set containing all the roots of a single irreducible polynomial over GF(q). Suppose that each field ele- ment in this construction is represented as a power of a primitive element x of GF(q), and to simplify notation, represent xi by its base-x logarithm i. Hence, one logarithm set in the construction will be S1={1,q.q7....qu-1} (5A.59) representing the roots X, mx(z). Another set in the con- struction, representing the minimum polynomial mx(z) of degree d', is (5A.60) The logarithms in Se may be calculated by a coset-like construction. In fact, if e is relatively prime to qd 