Page 228 - Hardware Implementation of Finite-Field Arithmetic

208 Cha pte r Se v e n

17. else
18. u(x) := u/x;
19. d := d − 1;
20. end if
21. end if
22. end for
If u(x) and v(x) are hold in registers with m + 1 bits, then reduc-
tions modulo f(x) are not needed for u(x) and v(x). If functions rshiftm
and lshiftm performing 1-bit right and left shifts, respectively, of bit
vectors with m + 1 bits (from 0 to m) are available, and if function
m2xvvm performing the bit-wise XOR of two bit vectors x and y with
m + 1 bits (x XOR y , x XOR y , . . . , x XOR y ) is also available, then
0 0 1 1 m m
if polynomials s(x), r(x), f(x), u(x), v(x), and a(x) are represented with
bit vectors with m + 1 bits (type poly_vectorm), the above algorithm
can be implemented as follows:

m
Algorithm 7.21—Extended Euclidean algorithm for inversion in GF(2 )
for i in 0 .. m loop
s(i) := f(i); r(i) := a(i); v(i) := 0;
u(i) := 0; auxm(i) := 0;
end loop;
u(0) := 1; d := 0;
for i in 1 .. 2*m loop
if r(m) = 0 then
r := rshiftm(r);
u := rshiftm(u);
d := d + 1;
else
if s(m) = 1 then
s := m2xvvm(s,r);
v := m2xvvm(v,u);
end if;
s := rshiftm(s);
if d = 0 then
auxm := s; s := r; r := auxm;
auxm := v; v := u;
u := rshiftm(auxm);
d := 1;
else u := lshiftm(u); d := d - 1; end if;
end if;
end loop;

where multiplications in steps 4, 5, 12, and 15 (Algorithm 7.20) are
implemented with the rshiftm function, division in step 18 (Algorithm
7.20) is implemented with the lshiftm function, and subtractions in
steps 9, 10 (Algorithm 7.20) are implemented with the m2xvvm
function. An executable Ada file EEA_inversion.adb, including
Algorithm 7.21, is available at www.arithmetic-circuits.org.