ould have a factor Z - a over GF(q). Hence, a is a member of a larger field, called an extension field of GF(q), which will now be constructed. Let Sd be the set of qd distinct polynomials over GF(q) of degree less than d in an indeterminate Z. That is, (5.103) Pseudonoise Generators It is well known that the qd distinct elements of GF(q) correspond to the polynomials of S evaluated at a root of an irreducible polynomial of degree d over GF(q). Therefore, let the field element x in GF(q) corresponding to the polynomial X(z) in Sd be given by (5.104) The representation (5.104) clearly indicates that GF(q) can be viewed as a vector space of dimension d over a scalar field GF(q) with 1, a, serving as a basis. While there is also an obvious correspondence between field elements X and polynomials X(z), the field element itself is not a poly- nomial in an indeterminate Z, but rather should be viewed as a "pseudopoly- nomial" in the basis element a. Addition of the elements x and y in the extension field, corresponding to the polynomials X(z) and Y(z) in Sd, corresponds to vector addition. x+yX(a)y(a)(xyi (5.105) More effort is required to rexpress the result of a multiplication operation in the same basis; specifically a polynomial multiplication modulo ma(z) must first be carried out to determine R(z), i.e., X(z)Y(z)=W(z)ma(z)+R(z), = (5.106) where R(z) is a member of Sd. Then, since a is a root of ma(z), it follows = X(a)Y(a) = R(a). (5.107) Hence, computation in GF(q) is often referred to as arithmetic modulo ma(z). 5.5.2 The LFSR as a Galois Field Multiplier In Section 5.2.3 the contents of a shift register after n shifts were considered to be coefficients of a polynomial R(n)(z), and successive register contents were related by the polynomial recursion (see (5.24)-(5.26)) (5.108) (5.109) where P(z)/Q(z) is the formal power series representation of {bn}. Suppose Q(z) = ma(z), (5.110) i.e., the characteristic polynomial of the sequence {bn} produced by a Galois- configured LFSR is irreducible over GF(q) and has root