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.

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.

In this paper, we derive a fast polynomial basis multiplier for GF(2m) defined by pentanomials xm+xk3+xk2+xk1+1 with 1 ≤ k1 < k2 < k3 ≤ m/2 using the presented method by Park and Chang. The proposed multiplier has the time delay TA+(2+⌈log2(m-1)⌉) TX or TA+(3+⌈log2(m-1)⌉) TX which is the lowest one compared with known multipliers for pentanomials except for special types, where TA and TX denote the delays of one AND gate and one XOR gate, respectively. On the other hand, its space complexity is very slightly greater than the best known results.

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 present a bit-parallel squarer for GF(2n) defined by an irreducible trinomial xn +xk +1 using a shifted polynomial basis. The proposed squarer requires TX delay and at most n/2 XOR gates, where TX is the delay of one XOR gate. As a result, the squarer using the shifted polynomial basis is more efficient than one using the polynomial basis except for k=1 or n/2.

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.

We propose a parallel pth powering method over an arbitrary finite field GF(pm). Using the proposed method, we present the explicit formulae for the computation of cubing over a ternary field GF(3m) which is defined by irreducible trinomials. We show that the field cubing computation for irreducible trinomials, which plays an important role in calculating pairing, can be implemented very efficiently.