MAT 3343, APPLIED ALGEBRA, FALL 2003

Handout 5: The representation of GF(16)

Peter Selinger

Let α be a root of the primitive polynomial x^{4} + x + 1 ∈ ℤ_{2}[x]. The non-zero elements of GF(16) = ℤ_{2}(α) = ℤ_{2}[x]/(x^{4} + x + 1) can be represented by the powers of α as follows:

Element  a^{0} a^{1} a^{2} a^{3}
0 = 0  0 0 0 0
α^{0} = 1  1 0 0 0
α^{1} =  α  0 1 0 0
α^{2} =  α^{2}  0 0 1 0
α^{3} =  α^{3} 0 0 0 1
α^{4} = 1 + α  1 1 0 0
α^{5} = α + α^{2} 0 1 1 0
α^{6} =  α^{2} + α^{3} 0 0 1 1
α^{7} = 1 + α  + α^{3} 1 1 0 1
α^{8} = 1  + α^{2}  1 0 1 0
α^{9} =  α  + α^{3} 0 1 0 1
α^{10} = 1 + α + α^{2}  1 1 1 0
α^{11} =  α + α^{2} + α^{3} 0 1 1 1
α^{12} = 1 + α + α^{2} + α^{3} 1 1 1 1
α^{13} = 1  + α^{2} + α^{3} 1 0 1 1
α^{14} = 1  + α^{3} 1 0 0 1
α^{15} = 1  1 0 0 0

Arithmetic in GF(16) can be easily performed using this representation. Addition is performed by representing elements as polynomials in α of degree less than 4. Multiplication is performed using the representation of nonzero elements as powers of α. For example,

\frac{1 + α + α^{3}}{1 + α^{2} + α^{3}} + α + α^{2} = \frac{α^{7}}{α^{13}} + α + α^{2}
= a^{−6} + α + α^{2} (since α^{15} = 1)
= a^{9} + α + α^{2}
= α + α^{3} + α + α^{2}
= α^{2} + α^{3}.

[Source: Gilbert, Modern Algebra with Applications]