On the Arithmetic Operations Over Finite Fields of Characteristic Three With Low Complexity

Abstract

In this paper, the Hermite polynomial representation is adapted as a new way to represent certain finite fields of characteristic three. We give the multiplication method to multiply two elements of F3<inf>n</inf> in the Hermite polynomial representation with subquadratic computational complexity by using a divide-and-conquer idea. We show that in some cases there is a set of irreducible binomials in the Hermite polynomial representation to obtain modular reduction with a lower addition complexity than the standard polynomial representation. We also investigate the matrix vector product method for the multiplication of the field elements represented by Hermite polynomials. © 2013 Elsevier B.V. All rights reserved.