Page 303 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 283

c = c + ≤ j ≤
5. j j s i + j , 0 m − 1
6. end if
m − 1
f
7. s i + m =∑ j = 0 s i + j j
8. end for
Assume that the conversion from pol ynomial to triangular basis is
implemented using Eq. (9.21), and the conversion from triangular to
polynomial basis is implemented using Eq. (9.20) as follows

c(m-1) := ctr(0);
for i in 1 .. m-1 loop
for j in 0 .. i loop
c(m-1-i) := m2xor(c(m-1-i),m2and(ctr(i-j),f(m-j)));
end loop;
end loop;

where Ctr and C represent the element in the triangular and
polynomial basis, respectively. Then the following algorithm
implements Algorithm 9.7, where A, B, and C are represented in
the polynomial basis and where bases conversions are performed
where required.

m
Algorithm 9.8—Multiplication over triangular basis for GF(2 )
-- Basi s conversion: Polynomial (A) to Triangular (Atr)
atr(0) := a(m-1);
for i in 1 .. m-1 loop
for j in 0 .. i-1 loop
atr(i) := m2xor(atr(i),m2and(atr(i-1-j),f(m-1-j)));
end loop;
atr(i) := m2xor(a(m-1-i),atr(i));
end loop;
-----------------------------------
for i in 0 .. m-1 loop
s(i) := atr(i); c(i) := 0; ctr(i) := 0;
end loop;
for i in 0 .. m-1 loop
if b(i) /= 0 then
for j in 0 .. m-1 loop
ctr(j) := m2xor(ctr(j),s(i + j));
end loop;
end if;
for j in 0 .. m-1 loop
s(i + m) := m2xor(s(i + m),m2and(s(i + j),f(j)));
end loop;
end loop;
-- Basis conversion: Triangular (Ctr) to Polynomial (C)
c(m-1) := ctr(0);
for i in 1 .. m-1 loop