Page 241 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 221

end loop;
for j in 0 .. k-2 loop
c(j) := m2xor(d(j),h(j));
end loop;
c(k-1) := m2xor(d(k-1),e(k-1));
for j in k .. (2*k-2) loop
if j < m-1 then
c(j) := m2xor(d(j),m2xor(e(j),h(j-k)));
end if;
end loop;
for j in (2*k-1) .. m-2 loop
c(j) := m2xor(d(j),m2xor(e(j),e(j-k)));
end loop;
c(m-1) := m2xor(d(m-1),h(m-k-1));
An executable Ada file mastrovito_multiplication_v2_trinomials,
adb, including Algorithm 7.25, is available at www.arithmetic-circuits
.org. The corresponding VHDL code describing the circuit mastrovito_
trinomials_multiplication.vhd is also available at the example page.
7.6.5 Pentanomials
A polynomial with five nonzero c oefficients, that is, fx () = x +
m
x 3 + x 2 + x 1 + , is called a pentanomial of degree m, where 1 ≤
k
k
k
1
k < k < k ≤ m – 1. Irreducible pentanomials have drawn significant
1 2 3
attention also because using them can reduce the complexity of
finite field arithmetic in GF(2 ). Furthermore, it was proved in
m
[Ser98] that there exists either an irreducible trinomial or pentano-
mial of degree m ∈ [2, 10,000], therefore an irreducible pentanomial
can be used whenever an irreducible trinomial of degree m does not
exist. Several classes of pentanomials have been considered in the
literature ([ZP01], [RK03], [RH04], [IHT06]).
Let us consider one of the special classes of irreducible pentano-
mials proposed in [ZP01] known as Class 1 pentanomials, for which
k ≤ m/2. Let us also c onsider pentanomials such as k = k – k . In such
3 1 3 2
a case, the product C = D + P E given in Eq. (7.29) can be computed as
T
follows.
Let h s be intermediate in terms defined as follows [RH04]:
j
h = e + e 0 ≤ j ≤ k − 2 (7.66)
−
+
+
−
j j m k 3 j m k 2 2
0 ( )
The above terms can be used to generate e , 0 ≤ j ≤ k – 2, given
j
2
in Eq. (7.52) by substituting t = 3 in Eq. (7.52) as follows:
⎧ e + h + e ; 0 ≤ j ≤ k − 2
−
+
⎪ j j j m k 1 1
−
1
j
⎪ ⎪ e + h ; k − ≤ ≤ k − 2
1
2
j
j
1
j
e () 0 = ⎨ e + e ; k − ≤ ≤ k − 2 (7.67)
−
j j + j m k 2 3
⎪ 3
1
j
⎪ e ; k 3 −≤ ≤ m − 2
j
⎪ ⎩ 0 ; j = m − 1
−