Page 194 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 175

First, we introduce a matrix notation [Paa94] for the multiplication
m
c(x) = a(x)b(x) mod f(x) in the field GF(2 ). All elements are binary
polynomials of degree less than m:

c x m − 1 . . . + c x + c = (a x m − 1 + . . . + a x + a )
+
m − 1 1 0 m − 1 1 0
(7.18)
(b x m − 1 + . . . + b x + b ) mod f(x)
m − 1 1 0
The elements b(x) and c(x) can also be represented as column vectors
with the polynomial coefficients. The matrix Z = h(a(x),f(x)) can be
introduced in such a way that the multiplication can be described as
⎛ c ⎞ ⎛ ⎛ b ⎞
⎜ c 0 ⎟ z 00 , z 0, m−1 ⎞ ⎜ b 0 ⎟
C = ⎜ 1 ⎟ = Z B = ⎜ ⎟ ⎜ 1 ⎟
⎜ ⎟ ⎜ z ⎜ z ⎟ ⎟ ⎜ ⎟ ⎟ (7.19)
−
1
⎝ c ⎜ m ⎠ ⎟ ⎝ m−10, m −1,m − ⎠ ⎜b − ⎠ ⎟
−1
⎝ m
1

T
where C = (c , c , . . . , c ) and B = (b , b , . . . , b ) are the vectors
T
0 1 m − 1 0 1 m - 1
associated with c(x) and b(x), respectively. The (m × m) matrix Z is
named the product matrix or Mastrovito matrix. Its coefficients z ∈
i,j
GF(2) depend recursively on the coefficients a and on the coefficients
i
p of the P matrix [introduced in Eq. (7.21)] as follows:
i,j
⎧ ⎪ aj = 0 i ; = 0 ... , m − 1
,
;
i
z = ⎨ j−1 (7.20)
+
,
ij ui − j a ij ∑ p a ;, , m − 1; j ≠ 0
)
(
j i = 0, ...
⎩ ⎪ − t=0 j− −1 t,iim−−1 t
where the step function u(μ) is 1 for μ≥ 0 or 0 for μ < 0. The matrix-
vector product given in Eq. (7.19) describes the entire field of
multiplication [Paa94]. The P matrix required for the computation
of the Z matrix is a function of the irreducible polynomial f(x) of
degree m. Its binary entries p are defined below
i,j
⎛ x m ⎞ ⎛ 1 ⎞ ⎛ p , 00 p , 0 m−1 ⎞ ⎛ 1 ⎞
⎜ x m+ ⎟ ⎜ x ⎟ ⎜ p p ⎟ ⎜ x ⎟
1
⎜ ⎟ = ⎜ ⎟ mmod fx () = ⎜ , 10 , 1 m−1 ⎟ ⎜ ⎟ mod fx
()
P
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
x ⎝
⎜ 2 m− ⎟ ⎠ x ⎝ m−1 ⎠ ⎜ ⎝ p m−20 p m−2,m − ⎠ ⎟ ⎝x m −1 ⎠
2
−
,
1
(7.21)
The binary entries p of P given in Eq. (7.21) can be recursively
i,j
computed in the function of the coefficients of the irreducible
m
polynomial f(x) = x + f x m − 1 + . . . + f x + f as follows:
m − 1 1 0
⎧ ⎪ p i ; = 1 ... , m − 2 j ; = 0
,
p = ⎨ i−1 , m−1 ; i = ,m − j = ,m − (7.22)
+
,
ij
p
⎩ ⎪ p i−1 j , −1 p i−1,m− 1 0,j 1, ... 2; 1,... 1
1