Page 182 - Hardware Implementation of Finite-Field Arithmetic

164 Cha pte r Se v e n

Polynomial basis is more promising in the sense that it gives
designers more freedom on irreducible polynomial selection and
hardware optimization. Among the important irreducible poly-
nomials usually selected, trinomials, pentanomials, ESPs (equally-spaced
polynomials), and AOPs (all-one polynomials) can be considered.

7.1 Multiplication
In Chap. 5, the multiplication modulo f(x) has been dealt with in the
general case where the basic field is Z . In this section, we will consider
p
as basic field the binary field Z = GF(2).
2
Let f(x) be a degree m irreducible polynomial over GF(2) in the
form
m
f(x) = x + f x m − 1 + . . . + f x + f (7.1)
m − 1 1 0
where f ∈ GF(2) = {0, 1}. Then, the set {1, x, . . . x m − 1 } is the polynomial
i
m
basis in GF(2 ), and we can represent arbitrary elements in GF(2 )
m
defined by f(x) as a(x) = a x m − 1 + . . . + a x + a , where a ∈ GF(2).
m − 1 1 0 i
Let a(x) and b(x) be two field elements and c(x) be their product.
Then,
c(x) = a(x)b(x) mod f(x) (7.2)
Thus, the polynomial basis multiplication involves two steps:
polynomial multiplication and reduction modulo an irreducible polynomial .
The product d(x) of the polynomials representing the field elements
a(x) and b(x), d(x) = a(x)b(x), is a degree 2m – 2 polynomial. In the
modular reduction c(x) = d(x) mod f(x), the degree 2m – 2 polynomial
d(x) is reduced by the degree m irreducible polynomial f(x) iteratively.
The choice of the irreducible polynomial f(x) may ease the modular
reduction. Sparse irreducible polynomials having fewer nonzero
terms are usually preferred for efficiency. In Sec. 7.6, important
irreducible polynomials will be considered.
Several algorithms can be used for the implementation of the
field multiplication given in Eq. (7.2).

7.1.1 Two-Step Classic Multiplication
The two-step classic multiplication in GF(2 ) is a straightforward
m
translation of the classic school multiplication algorithm, and cor-
responds to the binary version of the two-step multiplication given
in Chap. 5. In the two-step multiplication, the field product c(x)
given in Eq. (7.2) involves two steps: polynomial multiplication and
reduction modulo an irreducible polynomial.
The product d(x) of the polynomials a(x) and b(x), d(x) = a(x)b(x),
is a polynomial with maximum degree 2m − 2. Polynomial multipli-
cation d(x) can be written in matrix form [RSDK06] as: