Page 300 - Hardware Implementation of Finite-Field Arithmetic

280 Cha pte r Ni ne

end loop;
for i in 0 .. 2*m-2 loop s(i) := h(i); end loop;
s(2*m-1) := m2xor(h(2*m-1),1);
-- Algorithm
p(0) := 1; q(0) := 1; L := 0; s(0) := a(m-1);
for i in 1 .. 2*m loop
d := 0;
for j in 0 .. L loop
d := m2xor(d,m2and(p(j),s(i-1-j)));
end loop;
if (i-1-2*L) >= 0 then e := d; else e := 0; end if;
Paux := P; Qaux := Q;
P := m2xvvm(Paux,m2abvm(d,rshiftm(Qaux)));
Q := m2xvvm(m2abvm(e,Paux),m2abvm(m2xor(1,e),rshiftm
(Qaux)));
L := bit2int(e)*(i - L) + bit2int(m2xor(1,e))*L;
if i in 1..m-1 then
s(i) := 0;
for j in 0 .. i-1 loop
s(i) := m2xor(s(i),m2and(s(i-1-j),f(m-1-j)));
end loop;
s(i) := m2xor(a(m-1-i),s(i));
elsif i in m..2*m-2 then
s(i) := 0;
for j in 0 .. m-1 loop
s(i) := m2xor(s(i),m2and(s(i-1-j),f(m-1-j)));
end loop;
elsif i = 2*m-1 then
s(i) := 0;
for j in 0 .. m-1 loop
s(i) := m2xor(s(i),m2and(s(i-1-j),f(m-1-j)));
end loop;
s(i) := m2xor(1,s(i));
end if;
end loop;
for i in 0 .. m-1 loop g(i) := p(m-i); end loop;
for i in 0 .. m-1 loop b(i) := m2xor(g(i),f(i));
end loop;

where the first instructions in Algorithm 9.5 compute the h and s
i i
terms given in Eqs. (9.23) and (9.25), respectively. An executable Ada
file poly_inv_triangular_inv.adb, including Algorithm 9.5 is available
at www.arithmetic-circuits.org.
Algorithm 9.4 can be used for performing the inversion of an
m
element A ∈ GF(2 ), A = B, with A represented in the triangular basis
−1
and B represented in the polynomial basis as follows [HW00]. The
first m elements of the sequence of s terms in Algorithm 9.4 are
i
essentially the coordinates of A in the triangular basis: s = a in step 2.
0 m − 1
Assignment of s for 1 ≤ i ≤ m − 1 in step 8 of Algorithm 9.4 correspond
i
a
to Eq. (9.21). Therefore, s = ,0 ≤ i ≤ m − 1 in Algorithm 9.4. If A is
i
i
represented in triangular basis with coefficients a , 0 ≤≤ m 1− , then
i
i