Primitivity Test (a) i=1. (b) Ni(z) = z(9d-1)/p mod A(z). (c) If Ni(z) = 1, then [A(z) is not primitive. STOP]. (d) If i<J, then [i = i + 1, Go to (b)]. (e) A(z) is primitive. STOP. Step (b) in this test checks to see if the exponent of A(z) lacks the prime factor pi, which, if this is the case, results in Ni(z) = 1. The difficult part of this test is to determine the prime decomposition of q₫ - 1. A decom- position table for the case q = 2, for 1 d < 120 is included in Appendix 5B. A selected table of primitive polynomials over this range of parame- ters is also included in Appendix 5B, along with references to more exten- sive listings. 5A.8. Properties of Minimum Polynomials Once a primitive polynomial mx(z) of degree d over GF(q) has been deter- mined, the elements of GF(q) (excluding zero), can be represented as pseudopolynomials in x or as powers of x and addition and multiplication operations defined. The minimum polynomials of the remaining field ele- ments of GF(q) can be calculated directly. Suppose that y is another element of GF(q) and its minimum polynomial is desired. Knowledge of y as a power of x allows the exponent of y to be Appendix 5A. Finite Field Arithmetic determined as in Section 5A.6. This provides the following additional infor- mation. THEOREM 5A.11. Let y be an element of exponent e in an extension field of GF(q). Then the following are equivalent statements: (a) d is the smallest integer for which eqd - 1. (b) GF(q) is the smallest field containing y. (c) d is the degree of the minimum polynomial of y over GF(q). Proof. Let a be the smallest integer such that eqa - 1; let b be the small- est integer such that y E GF(qb); let C be the degree of the minimum poly- nomial of y over GF(q). The results of previous sections justify the following relations: y is a root of (b) y GF(qb) y is a root (c) my(z) irreducible of degree my,(2)|z4° - z = (d) Since ascsbsa,a= b=c. It is now possible to find the minimum polynomial over GF(q) of a field element y. Linear Equation Algorithm for Determining