Efficient parallel multiplier in shifted polynomial basis
In this paper we study the multiplication in fields F2n F 2 n using the Shifted Polynomial Basis (SPB) representation of Fan and Dai [H. Fan, Y. Dai, Fast bit-parallel GF(2n) multiplier for all trinomials, IEEE Transactions on Computers 54 (4) (2005) 485490]. We give a simpler construction than in Fan and Dai (2005) of the matrix associated to the SPB used to perform the field multiplication. We present also a novel parallel architecture to multiply in SPB. This multiplier have a smaller time complexity (for good field it is equal to TA+?log2(n)?TX) than all previously presented architecture. For practical field F2n F 2 n , i.e., for n?163, this roughly improves the delay by 10%. On the other hand the space complexity is increased by 25%: the space complexity is a little greater than the time gain.
parallel multiplier shifted polynomial basis binary field