A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials


ÖZBUDAK F., AKLEYLEK S., Cenk M.

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, no.10, pp.2016-2024, 2013 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Publication Date: 2013
  • Doi Number: 10.1587/transfun.e96.a.2016
  • Journal Name: IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.2016-2024

Abstract

In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the product of two elements in Hermite polynomial representation can be performed as Toeplitz matrix-vector product. This representation is very interesting for NIST recommended binary field GF(2(571)) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.