In this paper, we present a new three-way split formula for binary polynomial multiplication (PM) with five recursive multiplications. The scheme is based on a recently proposed multievaluation and interpolation approach using field extension. The proposed PM formula achieves the smallest space complexity. Moreover, it has about 40% reduced time complexity compared to best known results. In addition, using developed techniques for PM formulas, we propose a three-way split formula for Toeplitz matrix vector product with five recursive products which has a considerably improved complexity compared to previous known one.

We propose subquadratic space complexity multipliers for any finite field $mathbb{F}_{q^n}$ over the base field $mathbb{F}_q$ using the Dickson basis, where q is a prime power. It is shown that a field multiplication in $mathbb{F}_{q^n}$ based on the Dickson basis results in computations of Toeplitz matrix vector products (TMVPs). Therefore, an efficient computation of a TMVP yields an efficient multiplier. In order to derive efficient $mathbb{F}_{q^n}$ multipliers, we develop computational schemes for a TMVP over $mathbb{F}_{q}$. As a result, the $mathbb{F}_{2^n}$ multipliers, as special cases of the proposed $mathbb{F}_{q^n}$ multipliers, have lower time complexities as well as space complexities compared with existing results. For example, in the case that n is a power of 3, the proposed $mathbb{F}_{2^n}$ multiplier for an irreducible Dickson trinomial has about 14% reduced space complexity and lower time complexity compared with the best known results.

A field multiplication in the extended binary field is often expressed using Toeplitz matrix-vector products (TMVPs), whose matrices have special properties such as symmetric or triangular. We show that such TMVPs can be efficiently implemented by taking advantage of some properties of matrices. This yields an efficient multiplier when a field multiplication involves such TMVPs. For example, we propose an efficient multiplier based on the Dickson basis which requires the reduced number of XOR gates by an average of 34% compared with previously known results.

In several important applications, we often encounter with the computation of a Toeplitz matrix vector product (TMVP). In this work, we propose a k-way splitting method for a TMVP over any field F, which is a generalization of that over GF(2) presented by Hasan and Negre. Furthermore, as an application of the TMVP method over F, we present the first subquadratic space complexity multiplier over any finite field GF(pn) defined by an irreducible trinomial.

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(2571) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.