Page 237 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 217

⎛111 111⎞
⎜1 00 000 ⎟
⎜
P = 0 1 0 000 ⎟ ⎟ (7.55)
⎜
⎜ ⎟
⎜ ⎜ ⎝000 1 00⎠ ⎟
Using Eq. (7.55), we see that the product or Mastrovito matrix Z can be
decompose d as the sum of the following two matrices Z and Z [KS98]:
1 2

⎛ a 0 a a a ⎞
⎜ 0 m −1 m −2 2 ⎟
⎜ a 1 a 0 0 a m −1 a 3 ⎟
Z = ⎜ ⎟ (7.56)
1
a ⎜ a a a a 0 ⎟ ⎟
⎜ m −2 m −3 m− 4 m− 5 ⎟
⎝ a ⎜ m−1 a m−2 a m−3 a m− 4 a ⎟ ⎠
0
⎛ 0 a m− 1 a m− 2 a m− 3 a ⎞
1
⎜ ⎟
⎜ 0 a m− 1 a m− 2 a m− 3 a 1 ⎟
Z = ⎜ ⎟ (7.57)
2
⎜ 0 a a a a ⎟ ⎟
⎜ m m−1 m−2 m−3 1 ⎟
⎝ 0 a m−1 a m−2 a m−3 a ⎠
1
In order to compute the product C = ZB = (Z + Z )B, the two
1 2
vectors D = Z B and E = Z B can be computed in parallel and then
1 2
compute the result C = D + E. From Eq. (7.56), the coefficients d from
k
vector D can be computed as
k ∑
b +
d = k a k i i ∑ m−1 a b k = 0, ,....,m − 1 (7.58)
=+
i k
1 (
i=0 − ik 2 m−− − −2) i
and the coefficients e from vector E can be computed from Eq. (7.57) as
k
=
e = e = e = ... = e m− ∑ m−1 a b (7.59)
1
i
(
0 1 1 i=1 m− − −1) i
because Z is a matrix with identical rows. Finally, the coefficients c
2 k
from the result C will be
e d
c =+ k k = 0,... , m − 1 (7.60)
k
Algorithm 7.24—Mastrovito multiplication for AOPs
for j in 0 .. m-1 loop c(j) := 0; d(j) := 0; end loop;
e := 0;
for k in 0 .. m-1 loop