. If the exponent e of an element X equals the order q - 1 of the multiplicative group of GF(q), then x is termed a primitive field element. (It can be shown that the multi- plicative group of a finite field is cyclic.) Example 5A.11. In the Galois field of sixteen elements shown in Figure 5A.2, the element C is primitive. This can be verified from Table 5A.2. The addition and multiplication tables for GF(16), shown in Figure 5A.1, were constructed from Table 5A.2 in the following manner. An irreducible polynomial over GF(2) of degree 4, namely z4 + Z + 1 was known to have a primitive element as its root, which we named C. The powers of C were reduced to pseudopolynomials of degree 3 or less in c, since c4 + c + 1 = 0, Appendix 5A. Finite Field Arithmetic Table 5A.2 Representations of GF(16) Representations Element name Power of C Pseudopolynomial in C c + c2 c2 +c3 1+c+++ 1+ c2 1+c+c2 c + c + c 3 1+c+c+c3 c2 + c3 giving the representation columns in the table. Names were assigned as in the first column. The addition table of Figure 5A.1 was constructed using the pseudopolynomial representations and coefficient addition in GF(2); the multiplication table was constructed using the power representations and the fact that C15= 1. Obviously the table embodies the additive and multiplica- tive properties of the field. The representation columns of the table can be generated by shift registers storing the coefficients of C. Suppose a binary shift register is constructed as shown below, with the coefficient of ci shifting into the coef- ficient of ci+1. COEFFICIENT OF If 011010110000001 is present in the register, this represents C c6 + c7 + c 14. A single shift of the contents of the register corresponds to a multiplication by C. Hence, in the above example, 10110101100000 represents the register with 100000000000000, the successive contents of the register would have represented 1, c, c2, c3, above repre- Pseudonoise Generators sentation for multiplication by C only uses the fact that C has order 15. A sim- ilar shift