 my(z) over GF(q) (a) Determine the exponent of y. (b) Determine the degree d' of my (z) over GF(q). (c) Represent yi as a pseudopolynomial over GF(q) in X, x being a primi- tive element of the field GF(q) containing y, and the minimum poly- nomial of X being known. Hence, determine Aij in GF(q) such that (5A.53) (d) Find the coefficients bo, bd'-1 in the minimum polynomial my(z), such (5A.54) or equivalently, solve the following equations in GF(q) for boo....,bd-1: baaj0,d-1. (5A.55) (e) The minimum polynomial of y over GF(q) is . . . + biz+ bo. (5A.56) Pseudonoise Generators We shall illustrate this algorithm with an example using the description of GF(16) in Section 5A.6. Example 5A.13. Consider the element h in GF(16). (a) h = c7, C primitive, SO the order of h is 15/gcd (7, 15) = 15 (b) mh(z) over GF(2) has degree dm = 4 since 15 does not divide (2 - 1) 15 does not divide (22 - 1) 15 does not divide (23 - 1) 15 divides (24-1). (c) ho = 1 = 1 h1=c7=1+c+c3 h3=c6=c2+c (d) h4 + b3h3 + b2h2 + b1h bo = 0 gives for the coefficients of ci: i = = 0 i = 1:b1 = 0 i = 2:1 + b3 = 0 i = 3:1 + b3 + b2 + b1 = 0 which are easily solved over GF(2) to give bo = b3 = 1, b1 = b2 = 0. (e) The minimum polynomial of h over GF(2) is z4 + z3 + 1. Instead of specifying a monic polynomial by its coefficients, it can be described by listing its roots. DEFINITION 5A.7. The q-conjugates of X are the d - 1 roots of the minimum polynomial mx(z) of X over GF(q), after X has been excluded, d being the degree of mx(z). The q-conjugates of x are easily derived from x via the following theorem. THEOREM 5A.12. Let mx(z), the minimum polynomial of X over GF(q), have degree d. Then X, x9, xx, all distinct and are the d roots of mx(z). Proof. Using Theorem 5A.10, we have that Appendix 5A. Finite Field Arithmetic Hence, if x is a non-zero root of a polynomial over GF(q), then SO is x9. Iterating this line of reason we see that X, x9, x92, x93 , must all be roots of mx(z). We now show that x, are all distinct. Suppose = for 0i,j Multiplying both sides