iminated, and the elements of GF(16) viewed as the pseudopolynomials in C of degree Table 5A.1 Representations of elements in GF(16) as pseudopolynomials in C over GF(4) and GF(2). c-representation c-representation element over GF(4) over GF(2) c2 + c c2 + c + 1 bc + a c + 1 c + 1 c3 + c2 ac + b c3++++ c2 + 1 ac t a c3 +c bc + 1 c3+c2++++ ac + 1 c3+c2+1 bc +b c3 + 1 Pseudonoise Generators three or less. The structure of GF(16) arithmetic then is dictated by GF(2) arithmetic and the fact that c+++++ 0. 5A.5. The Construction of Finite Fields Using the structures uncovered in the previous section, it now is possible to construct finite fields. To first construct the integer subfield, note that the integers 0, 1, p - 1 are a commutative ring under addition and multi- plication modulo p. Hence, 0, 1, 2, ,p - 1 form a field under addition and multiplication mod p if the integers 1,2, - 1 have inverses under mul- tiplication mod p. THEOREM 5A.4. If p is prime, then 1,2,...,p - 1 all have inverses under multiplication mod p. Proof. Suppose 1 < j < p. Then, since p is prime, the greatest common divi- sor of j and p is 1. Hence, there exist integers n1 and N2 such that 1 = gcd(j,p)=nj+n2p (5A.34) Reducing both sides of the equation mod p gives 1 = ((n1 mod p)j) mod p (5A.35) Hence, n1 mod p is the inverse of j. THEOREM 5A.5. If p is not prime, then at least one element in the collection 1, 2, p - 1 does not have an inverse under multiplication mod p, and the collection is not closed under multiplication mod p. Proof. The integer p not prime means p = PiP2 for some P1 and P2 in the range 1 <p1 < p, 1 < P2 < p. Hence, under multiplication mod p 0 = p1p2 mod = p. (5A.36) If P2 had an inverse under multiplication mod p, the above equation would imply p1 mod p. (5A.37) Since P1 is a non-zero element of the ring, P2 cannot have an inverse under multiplication. Summarizing these results gives: THEOREM 5A.6. The integers 0, 1, p - 1 form a field under addition and multiplication mod p if and only if p is a prime number. The next 