Page 301 - Hardware Implementation of Finite-Field Arithmetic
P. 301
m
Operations over GF (2 )—Other Bases 281
B = A , with A represented in the triangular basis, can be performed by
−1
simply assigning s = ,0 ≤ i ≤ m − 1 in Algorithm 9.4. In any case, B is
a
i i
represented in the polynomial basis. Hence, the following algorithm
implements the inversion in triangular basis:
m
Algorithm 9.6 —Inversion over triangular basis for GF(2 )
-- Computation of h and s
h(0) := a(m-1);
for i in 1 .. m-1 loop
for j in 0 .. i-1 loop
h(i) := m2xor(h(i),m2and(h(i-1-j),f(m-1-j)));
end loop;
h(i) := m2xor(a(m-1-i),h(i));
end loop;
for i in m .. 2*m-1 loop
for j in 0 .. m-1 loop
h(i) := m2xor(h(i),m2and(h(i-1-j),f(m-1-j)));
end loop;
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(0);
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) := a(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;