Low-complexities Polynomial Basis And Gaussian Normal Basis Multipliers Design In Binary Extension Field

Finite field multiplication in GF(2m)is widely used in Elliptic curve cryptography(ECC),err correcting codes and Galois/counter mode(GCM).It is very important to explore efficient hardware architectures and low complexities finite field multiplications for these applications.For designing and implementing efficient multipliers,multiplication based on polynomial basis(PB)and Gaussian normal basis(GNB)receives more attention.Therefore,hight-performance and low-complexity multipliers based on PB and GNB are focused in this paper.The major research contents and results are concluded as the following:1)In finite filed GF(2m),multiplication based on PB is simple and regular,but the multiplication needs two operations,which are school multiplication and polynomial reduction.For reduce the complexity of reduction,some special polynomials are chose as the irreducible polynomial of reduction,like AOP(All One Polynomial)and ESP(Equally Spaced Polynomial),as well as trinomial and pentanomial later.As the important and classic approach,Karatsbua algorithm(KA)is used for subquadratic complexities multiplier architectures.In recent years,KA doesn't receive study further.Therefore,a new decomposition of KA is proposed,called as(b,2)-way splitting method.Based on the proposed(b,2)-way KA scheme,a low space complexity digit-serial multiplier is presented.Combining with k-way KA decomposition,a novel scalable GPB(Generalized Polynomial Basis)multiplier is derived.Analytical results show that the proposed multiplier could achieve the desired trade-off between space and time complexities.Our proposed multiplier is modular,regular,and suitable for very-large-scale integration(VLSI)implementations.It involves significantly less area complexity,less computation time and less energy consumption compared to the existing digit-serial and scalable multipliers.2)GNB,as a special class of NB(Normal Basis),succeed to the advantage of NB,which is square free.By basis conversion,GNB can be formed into Palindromic polynomial basis(PPB).Based on PPB,even-type GNB multiplication can be performed by the sum of two Toeplitz matrix-vector products(TMVPs).It is noted that one of matrices is a symmetric Toeplitz matrix.Therefore,using the symmetric Toeplitz matrix,a novel STMVP(Symmetric TMVP)decomposition is proposed.Two-way STMVP decomposition can split 2 multiplication points,which involves one STMVP point and one TMVP point.Three-way STMVP decomposition can transform 5 multiplication points,which involves 2 STMVPs and 3 TMVPs.Combined with the TMVP approaches,two-way and three-way STMVP are performed for achieving subquadratic space complexity.According to synthesis results,the proposed STMVP has lower area,lower power and lower delay-area product compared to the existing Karatsuba algorithm and TMVP decomposition.3)Even-type GNB multiplication can be performed as C = T A + HA,where T A is a TMVP and HA is a HMVP(Hankel Matrix-Vector Product).Since T is a symmetric Toeplitz matrix,a symmetric matrix is defined as S = T + H,which is a sum of a symmetric Toeplitz matrix and a Hankel matrix.Then GNB multiplication is performed as a SMVP(Symmetric Matrix-Vector Product),denoted as C = S A.Applying the symmetry property,n-way splitting method of SMVP is presented.4)Based on PPB,even-type GNB multiplication can be represented by the sum of a HMVP and a TMVP.Applying the two-way TMVP approach,an addition of HMVP and TMVP scheme is proposed.Combining with Palindromic polynomial decomposition and partial products,GNB multiplication is implemented by a digit-serial architecture.According to the theoretical analysis,the proposed digit-serial multiplier has a lower complexities and a better trade-off between time and space complexities.In this paper,based on KA and TMVP approaches,(b,2)-way KA,STMVP decomposition and SMVP decomposition are proposed.The three approaches are benefited to design and implement high-performance and low-complexity multipliers.