Page 181 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 7

Operations over

m
GF (2 )—Polynomial

Bases

he goal of this chapter is the study of the operations over the

m
binary field GF(2 ) , where the elements of the finite field are
Trepresented in the polynomial basis.
Let α ∈ GF(2 ) and be a root of the irreducible polynomial f(x) =
m

m
x + f x m − 1 + . . . + f x + f over GF(2). Then, the set {1, α, . . . , α m − 1 }
m − 1 1 0
m
constitutes the polynomial basis in GF(2 ). With polynomial basis, the
m
elements in GF(2 ) can be represented as polynomials of degree at
m
most m – 1 in the form GF(2 ) = {a(α)|a(α) = a α m − 1 + . . . + a α + a ,
m − 1 1 0
a ∈ GF(2)}, where the coefficients a are the polynomial basis coordi-
i i
nates in GF(2). Polynomial basis can also be represented as the set
m
2
{1, x, x , . . . , x m − 1 } and, therefore, GF(2 ) = {a(x)|a(x) = a x m − 1 + . . . +
m − 1
a x + a , a ∈ GF(2)}. Arithmetic operations in GF(2 ) are performed
m
1 0 i
modulo an irreducible polynomial f(x) over GF(2). Addition of poly-
nomials is carried out under modulo 2 arithmetic. Therefore, the
addition of two polynomials becomes the bitwise exclusive-or (XOR)
of their binary representations. Subtraction is exactly the same as
addition in modulo 2 arithmetic, so 1 – x equals 1 + x.
Among the GF(2 ) arithmetic operations, multiplication is usually
m
considered the most important, complex, and time-consuming
operation. Complexity could depend on many factors, such as the
selection of the irreducible polynomial or the basis selected for the
m
representation of the field elements. A number of efficient GF(2 )
multiplication approaches and architectures have been proposed in
which different basis representations of field elements are used.
Among them, the most widely used are the polynomial (or standard or
canonical) basis and normal basis ; although other bases can also be
used. The complexity of basis conversion is heavily dependent on the
irreducible polynomial selected. If the polynomial is adequately
chosen, the basis conversion is a simple operation.
163