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;
   296   297   298   299   300   301   302   303   304   305   306