 register using the additional fact that C4 = C + 1, is shown below. COEFFICIENT OF A shift (multiplication by c) of the C3 coefficient results in C4 = C + being added to the contents of the register. If this register is started with 1000, the register contents after each shift will represent 1, c, c2, c13, c14, The representations will be pseudopolynomials of degree 3 or less in c, i.e., the pseudopolynomials in Table 5A.2. The multiplicative order of each element in a field GF(q) can be deter- mined from the representation table. To determine the order of ci where C is primitive, we first compute the gcd (i, qd - - 1). Then the smallest number e for which e is a multiple of qd - (5A.42) Hence, e is the order of ci. It can be shown that all the roots of an irreducible polynomial have the same order. Hence, an irreducible polynomial can be labelled with the order of its roots. An irreducible polynomial with a primitive field element as its root is called a primitive polynomial. The number of primitive polynomials Np(d) of degree d over GF(q) is given by (5A.43) where Pi,i=1,...,Jare the distinct primes which divide q₫ - 1. Certainly Np(d) is greater than zero for all powers of a prime as represented by q, and all degrees d. As a result every finite field can be constructed using a prim- itive irreducible polynomial. Example 5A.12. In GF(16) the orders of the elements are as follows: has order 1 c5, c10 have order 3 c3,c6,c9,c12 have order 5 have order 15. Appendix 5A. Finite Field Arithmetic Excluding the elements of GF(4), namely 0, 1, c5, and c10, any of the remain- ing twelve elements could be used to generate GF(16) as C did in Section 5A.5, and, hence, all must be roots of irreducible polynomials of degree 4. From the previous section, the number N(4) irreducible polynomials of degree 4 over GF(2) is =1[24 - 22] = 3, while the number Np(4) of primitive irreducible polynomials of degree 4 over GF(2) is Hence, the nonprimitive elements c3, c6, c9, C12 must be roots of the same irre- ducible degree-4 polynomial