14:332:548, E
or Control Coding
Homework 3
Rutgers University
1. (a) Show that the polynomial X2 + 1 is i
educible over GF (3).
(b) Construct GF (32) using X2 + 1 as an i
educible polynomial (describe its addition and multi-
plication table). Also, give the power representation and vector representation of each element
of GF (32)
2. (a) Show that the polynomial X5 +X3 + 1 is i
educible over GF (2).
(b) Let α be a primitive element inGF (24). Use Table 3.3 in the slides to find the roots of f(X) =
X3 + α6X2 + α9X + α9.
3. Suppose we constructGF (23) using x3+x2+1 as an i
educible polynomial. Express each nonzero
element of GF (23) as a power of a primitive element of GF (23).
4. Let F = GF(2) and suppose that the field Φ = GF
(
24
)
is represented as binary polynmials modulo
the i
educible polynomial x4 +x3 +x2 +x+1. Show that in this representation, α+1 is a primitive
element in Φ, where α is a root of x4 + x3 + x2 + x+ 1.
5. Let F be a field and Φ be an extension field of F with extension degree [Φ : F ] = h <∞. Let β be
an element in Φ and denote bym the smallest positive integer such that the elements 1, β, β2, . . . , βm
are linearly dependent over F .
(a) Verify that m ≤ h.
(b) Show that if a(x) is a nonzero polynomial in F [x] such that a(β) = 0, then deg a(x) ≥ m.
(c) Show that there exists a unique monic polynomial Mβ(x) of degree exactly m over F such
that Mβ(β) = 0. (A monic polynomial is a polynomial in which the leading coefficient (the
nonzero coefficient of highest degree) is equal to 1.)
(d) Show that the polynomial Mβ(x) is i
educible over F .
(e) Show that if a(x) is a nonzero polynomial in F [x] such that a(β) = 0, then Mβ(x) divides
a(x).
Hint: Show that β is a root of the remainder polynomial obtained when a(x) is divided by
Mβ(x).
(f) Let F = GF (2) and Φ = F [ξ]/(ξ3 + ξ + 1). Compute the polynomial Mξ3(x).
Hint: Identify the representations in F 3 of ξ3i for i = 0, 1, 2, 3 according to the basis Ω(1 ξ ξ2).
Then check the linear dependence of those representations.
1