Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity

Abstract

In this paper, we give a new way to represent certain finite fields GF(2n ). This representation is based on Charlier polynomials. We show that multiplication in Charlier polynomial representation can be performed with subquadratic space complexity. One can obtain binomial or trinomial irreducible polynomials in Charlier polynomial representation which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. This representation is very interesting for NIST recommended binary field GF(2283) since there is no ONB for the corresponding extension. We also note that recommended NIST and SEC binary fields can be constructed with low weight Charlier polynomials. © 2010 Springer-Verlag Berlin Heidelberg.