. The eight elements of order 15 must be roots of the two degree-4 primitive polynomials. 5A.7. Finding Irreducible and Primitive Polynomials Some fundamental ideas are necessary before further progress can be made. The following are stated without proof: (a) A finite field of specified size is unique. This means that different irre- ducible polynomials of the same degree over the same ground field must lead to the same extension field structure. (b) GF(q) C GF(q) d'd. This is a dimensionality constraint that comes from viewing GF(q) as the result of a construction employing a poly- nomial of degree d/d' over GF(q). (c) All roots of an irreducible polynomial lie in the same field. If this were not the case, the construction of Section 5 might yield different exten- sion fields using the same polynomial. (d) The elements of GF(q) are the roots of the polynomial 29d-2 - Z. A proof of this fact follows directly from noting that the non-zero ele- ments of GF(q) have order dividing qd - 1 and, therefore, are roots of zqd-1 - 1. As a result of (a)-(d), it follows that the polynomial containing all elements of GF(q) as roots can be factored as follows: (5A.44) where Pd denotes the set of all monic irreducible polynomials of degree d over GF(q). Let A(z) be a polynomial of degree d over GF(q). The following algorithm can be used to determine if A(z) is irreducible. Pseudonoise Generators Irreducibility Test: (a) d' = 1. (b) N (z) = gcd(A(z), - z). (c) If # 1, then [A(z) has a factor STOP]. (d) If d' < [d/2], then [d' = d' + 1, Go to (b)]. (e) A(z) is irredicuble. STOP. Step (b) will recover any polynomial factors over GF(q) that are common to A(z) and - Z. If the test runs its full course for all d' in the range 1 VI d' < d/2, A(z) will have been checked for all possible irreducible factors of degree at most d/2. Since if A(z) is factorable, it must have a factor in this degree range, the test shows A(z) to be irreducible if and only if no factors are uncovered. Euclid's algorithm of Section 5A.2 can be mechanized to det