Page 240 - Hardware Implementation of Finite-Field Arithmetic

220 Cha pte r Se v e n

⎧ h ; 0 ≤≤ k − 2
j
⎪ j j =
⎪ e k −1 ; k − 1
⎪
c = d + ⎨ e + h ; k ≤ ≤ 2 k − 2 (7.61)
j
−
j j j j k
⎪ e + k − ≤ ≤
−
⎪ j j e j k ; 2 1 j m − 2
⎪ h mk 1 ; j = m − 1
⎩
−−

where h s can be obtained recursively as follows:
j
⎧ e + e ; k − 2 ≥ j ≥ 2 k − m − 1
⎪
−
+
h = ⎨ j j m k (7.62)
≥
j e + h ; 2 k − m − 2 ≥ j ≥ 0
+
−
⎩ ⎪ j j m k
It can also be found that for k = m – 1, Eq. (7.62) becomes
⎧ m−2 ≤≤
⎪∑
h = ⎨ ij e ; 0 j m − 2 7.63)
=
i
j h ; j = m − 1
⎩ ⎪ 0
Example 7.2 Multiplication in GF(2 ) for trinomial f(x) = x + x + 1
4
4
3
4
Let f(x) = x + x + 1 be the generating irreducible trinomial for GF(2 ).
4
3
From Fig. 7.12b, the P matrix is as follows:
⎛ 10 0 1⎞
⎜
P = 11 0 1 ⎟ (7.64)
⎜ ⎝ 11 11 ⎠ ⎟

T
From Eq. (7.64), the coordinates of the product C = D + P E given
in Eq. (7.29) can be computed as follows:
c = d + e + ( e + e ) = d + e + h = d + h
0 0 0 1 2 0 0 1 0 0
c = d + ( e + e )) = d + h = d + h
1 1 1 2 1 1 1 1 (7.65)
c = d + e = d + e = d + e
2 2 2 2 2 2 2
c = d + e + (e + e ) = d + e + h = d + h
(
3 3 0 1 2 3 0 1 3 0
where E and D vectors are computed as in Eq. (7.28). Coordinates in
Eq. (7.65) can also be obtained using Eqs. (7.61) and (7.62) or Eq. (7.63).
The following algorithm can be given for the computation of the
k
m
product using an irreducible trinomial f(x) = x + x + 1, with m/2 < k ≤
m – 1, which implements the expressions given in Eqs. (7.61) and (7.62).
Algorithm 7.25—Mastrovito multiplication for trinomials
d := vector_D(a,b);
e := vector_E (a,b);
for j in reverse (2*k-m-1) .. k-2 loop
h(j) := m2xor(e(j),e(j+m-k));
end loop;
for j in reverse 0 .. (2*k-m-2) loop
h(j) := m2xor(e(j),h(j+m-k));