Mastrovito multiplier for all trinomials
Berk Sunar, Çetin Kaya Koç · IEEE Transactions on Computers · 1999
An efficient algorithm for the multiplication in GF(2/sup m/) was introduced by Mastrovito. The space complexity of the Mastrovito multiplier for the irreducible trinomial x/sup m/+x+1 was given as m/sup 2/-1 XOR and m/sup 2/ AND gales. In this paper, we describe an architecture based on a new formulation of the multiplication matrix and show that the Mastrovito multiplier for the generating trinomial x/sup m/+x/sup n/+1, where m/spl ne/2n, also requires m/sup 2/-1 XOR and m/sup 2/ AND gates, However, m/sup 2/-x/sup m/2/ XOR gates are sufficient when the generating trinomial is of the form x/sup m/+x/sup m/2/+1 for an even m. We also calculate the time complexity of the proposed Mastrovito multiplier and give design examples for the irreducible trinomials x/sup 7/+x/sup 4/+1 and x/sup 6/+x/sup 3/+1.