Efficient parallel multiplier in shifted polynomial basis

In this paper we study the multiplication in fields F2nF2n 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) 485–490]. 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 F2nF2n, 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.