On bit-serial multiplication and dual bases in GF(2m)

The existence of certain types of dual bases in finite fields GF(2 ^m) is discussed. These special types of dual bases are needed for efficient implementation of (generalized) bit-serial multiplication in GF(2^m). In particular, the question of choosing a polynomial basis of GF(2^m), for example {1, α, α ², α³, . . ., α^m-1}, such that the change of basis matrix from the dual basis to a scalar multiple of the original basis has as few `1´ entries as possible, is studied. It was previously shown by M. Wang and I. F. Blake (1990) that the optimal situation occurs when the minimal polynomial of α is an irreducible trinomial of degree m; then, an appropriate scalar multiple, β, yields a change of basis matrix that is a permutation matrix. A construction is presented that often yields bases where the change of basis matrix has low weight, in the case where no irreducible trinomial of degree m exists. A simple formula can be used to compute β and the weight of the change of basis matrix, given the minimal polynomial of α