agjkbmpq1 0ejpfaghkbmnq lca ofkqaghjbmnplcde 10gmchjkbnpqdefa h hndjkbmpqlcefa j jpekbmnqlcdfagh 0kqfbmplcdeagh J0mcgnpqldefahjkb n 0ndhpqlefagjkbn pejqlcdfaghkbmn 90qfklcdeaghjbmnp Figure 5A.1. Addition and multiplication in GF(16). The minimum polynomial of a field element X over a subfield GF(q) must exist since it has already been demonstrated that at least one polynomial over GF(q) having X as a root, exists. It can also be shown that the minimum polynomial of x is unique and irreducible over GF(q). Suppose we now investigate the collection V of all elements of the form (5A.30) Appendix 5A. Finite Field Arithmetic (5A.31) where the coefficients a are in GF(q), X is a field element not in GF(q), and dm is the degree of the minimum polynomial of x over GF(q). (a) For two distinct vectors a and b of dimensions dm, Va # Ub. Proof. Assume Va=Vb Then Va-b is a pseudopolynomial of degree dm - 1 or less in X with coefficients in GF(q) which is equal to 0. But the minimum polynomial of x has degree dm, and, hence, Va # Vb. (b) V is closed under addition. Proof. (5A.32) (c) 9 is closed under multiplication. Proof. 2(dm-1) (5A.33) where C is in GF(q). By the Euclidean division algorithm for polynomials in an indeterminate, C(z) = Q(z)mx(z) + R(z), deg R(z) < deg mx(z) = dm. Now since mx(x) = 0, substitution of x for Z. gives C(x) = R(x), a pseudopoly- nomial in the field element x of degree less than dm with coefficients in GF(q). Since this subset 9 of the field is closed under addition and multiplication, we have the following result: THEOREM 5A.3. Let GF(q) be a subfield of a larger field and let x be a field element not in GF(q), the minimum polynomial mx(z) of X over GF(q) hav- ing degree dm. Then the pseudopolynomials in x over GF(q), having degree less than dm are the distinct elements of a field GF(qdm). Example 5A.10. Consider the addition and multiplication tables of GF (16) shown in Figure 5A.1. Forming pseudopolynomials in a over GF(2), and eval- uating them using Figure 5A.1 gives Pseudonoise Generators = 