Page 227 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 207

m
inversion over GF(2 ) are mainly based on Fermat’s theorem and on
Euclid’s algorithm . Using Fermat’s theorem, the inverse of an element
m
in GF(2 ) can be found by successive squaring and multiplication. In
normal basis representation of a Galois field, squaring is done by a
simple cyclic shift. Hence, the algorithms based on Fermat’s theorem
for inversion mainly choose this basis ([IT88], [Fen89], [ABMV93]).
Euclid’s algorithm for polynomials calculates the greatest com-
mon divisor (gcd) polynomial of two polynomials. The algorithm
can be extended for calculating the two polynomials, u(x) and
w(x), that satisfy gcd(a(x),b(x)) = u(x) × a(x) + w(x) × b(x). The
extended Euclid’s algorithm has been studied in Chap. 6. Let f(x)
be the irreducible polynomial with degree m that defines the field,
and a(x) be the polynomial representation of an element in the
field. Since the greatest common divisor polynomial of a(x) and
f(x) is 1, the multiplicative inverse a (x) of a(x) can be obtained as
− 1
u(x) mod f(x) by replacing b(x) with f(x), that is, gcd(a(x), f(x)) = u(x) ×
a(x) + w(x) × f(x). Therefore, 1 = u(x) × a(x) mod f(x), and finally a (x) =
− 1
u(x) mod f(x).
An optimized algorithm for inversion in GF(2 ) based on the
m
extended Euclid’s algorithm is the following ([KTT07], [BCH93]). The
algorithm tests only the mth coefficients of two polynomials in the
computation of the gcd. The algorithm follows showing {Op1, Op2},
which means that the two operations, Op1 and Op2, are performed in
parallel. Furthermore, r and s denote the mth coefficients of the
m m
polynomials r(x) and s(x), respectively, and d holds the difference of
deg(r(x)) and deg(s(x)), where deg(⋅) represents the upper bound of
the degree of the proper one [KTT07].

m
Algorithm 7.20—Algorithm for inversion in GF(2 )
Input: a(x), f(x)
Output: u(x) = a (x)
-1
1. s(x) := f(x); v(x) := 0; r(x) := a(x); u(x) := 1;
d := 0;
2. for i = 1 to 2m do
3. if r = 0 then
m
4. r(x) := x × r(x);
5. u(x) := x × u(x);
6. d = d + 1;
7. else
8. if s = 1 then
m
9. s(x) := s(x) − r(x);
10. v(x) := v(x) − u(x);
11. end if
12. s(x) := x × s(x);
13. if d = 0 then
14. {r(x) := s(x), s(x) := r(x)};
15. {u(x) := x × v(x), v(x) := u(x)};
16. d := 1;