HP Labs Technical Reports

Efficient Arithmetic in GF (2 super n) through Palindromic Representation

Blake, Ian F; Roth, Ron M.; Seroussi, Gadiel

HPL-98-134

Keyword(s): finite field representation; optimal normal basis; palindromic representation

Abstract: A representation of the field GF(2 super n) for various values of n is described, where the field elements are palindromic polynomials, and the field operations are polynomial addition and multiplication in the ring of polynomials modulo x (super 2n+1)-1. This representation can be shown to be equivalent to a field representation of Type-II optimal normal bases. As such, the suggested palindromic representation inherits the advantages of two commonly-used representations of finite fields, namely, the standard (polynomial) representation and the optimal normal basis representation. Modular polynomial multiplication is well suited for software implementations, whereas the optimal normal basis representation admits efficient hardware implementations. Also, the new representation allows for efficient implementation of field inversion in both hardware and software.

3 Pages

Back to Index