Efficient Multiplier Design For Finite Fields GF(2~m)

The finite field GF（2^m）arithmetic has many important applications in cryptog-raphy and error-correcting code.Among the GF（2^m）arithmetic operations,mul-tiplication is one of the most important operation,because other costly operations such as exponentiation and inversion can be carried out by iterative multiplications.Therefore,it is necessary to design a highly efficient GF（2^m）multipliers.In 2013,Cilardo proposed the Generalized Polynomial Basis（GPB）,and gave the type C.1and type C.2 irreducible pentanomials.In 2014,Xiong et al.have constructed the efficient squarer of type C.1 pentanomials,whose complexity reached the current best result.The current multipliers for these two types of pentanomials have ful-ly considered the time complexity optimization,but considered a little about the trade-off between space and time complexity.Based on the parameters given by Cilardo and Xiong’s work,this paper constructed the type C.2 pentanomials squar-er and designed an efficient time-space trade-off multiplier for the above two types of pentanomial.The main contribution is as follows:1.We have constructed an efficient GPB squarer for type C.2 irreducible pen-tanomials.This paper give explicit GPB squarer formulae for all type C.2 irreducible pentanomials by reclassifying these pentanomials into certain sub-groups,which is based on the parities of pentanomial parameters.It is also proved that the newly constructed squarer achieves the best results so far.The numbers of XOR gates in this squarer is（2m+k₁-3）/2,the gate delay is 2T_X.2.We have constructed an efficient Montgomery multiplier for Type C.1 pen-tanomials.Based on a combination of generalized polynomial basis（GPB）and a divide and conquer approach,we can partition field multiplications into a compo-sition of sub-polynomial multiplications and Montgomery/GPB squarings.Conse-quently,the proposed multiplier roughly saves 1/4 logic gates compared with the fastest multipliers,while the time complexity matches previous multipliers using divide and conquer algorithms.3.An efficient Montgomery multiplier for a special class of type C.2 pentanomi-als is also developed.The new method use PCHS divide-and-conquer algorithm,which split a polynomial according to the parties of its term degree.On the basis of GPB square,we selected a new parameter R,which the montgomery factors depend on the smallest term degree（non constant）of the type C.2 pentanomial.Then the multiplier corresponding to the polynomial is constructed on the basis of the new parameters and the concrete multiplication formula is given.