On the arithmetic operations over finite fields of characteristic three with low complexity


Akleylek S., ÖZBUDAK F., Ozel C.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, vol.259, pp.546-554, 2014 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 259
  • Publication Date: 2014
  • Doi Number: 10.1016/j.cam.2013.08.011
  • Journal Name: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.546-554
  • Keywords: Finite field representation, Hermite polynomials, Modular multiplication, Matrix vector product method
  • Ondokuz Mayıs University Affiliated: No

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 F-3n 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. (C) 2013 Elsevier B.V. All rights reserved.