Page 302 - Hardware Implementation of Finite-Field Arithmetic

282 Cha pte r Ni ne

−1
In Algorithm 9.6, A is in triangular basis and B = A is in polynomial
basis.
Assume that the conversion fr om polynomial to triangular basis
is implemented using Eq. (9.21) as follows:

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

where Apol and A represent the element in the polynomial and
triangular basis, respectively. Then an executable Ada file triangular_
inv.adb, including an algorithm implementing Algorithm 9.6 and the
above basis conversion (hence with the input A given in polynomial
basis), is available at www.arithmetic-circuits.org.
Multiplication in triangular basis can be performed using the
above equations. Let C be the product of A and B, C = AB, with A,
B, C ∈ GF(2 ) and where A and C are represented in the triangular
m
basis. Applying Eqs. (9.23) and (9.25) to an algorithm for
multiplication given in [HB95], the following expression was given
in [HW00]:

⎛ s s s − ⎞ ⎛ b ⎞ ⎛ c ⎞
⎜ 0 1 m 1 ⎟ ⎜ 0 ⎟ ⎜ c 0 ⎟
⎜ s 1 s 2 s m ⎟ ⎜ b 1 ⎟ ⎜ 1 ⎟
⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ (9.26)
s ⎜ s s ⎟ b ⎜ m−2 ⎟ ⎟ ⎜c ⎟
−
−
−
⎜ m 2 m 1 2 m 3 ⎟ ⎜ b ⎟ ⎜ c m −2 ⎟
−
−
1
m 2
⎝ s m 1 s m s 2m− ⎠ ⎝ m− ⎠ ⎝ m 1 ⎠
which leads to the following algorithm for multiplication [HW00]:
Algorithm 9.7—Algorithm for multiplication over triangular basis
m
for GF(2 )
Input: A ∈ GF(2 ) in triangular basis, B ∈ GF(2 ) in
m
m
polynomial basis
Output: C = AB in triangular basis
a
1. s = , 0 ≤ j ≤ m − 1
j
j
2. c = 0, 0 ≤ j ≤ m − 1
j
3. for i = 0 to m - 1 do
4. if b i ≠ 0 then