New Bit Parallel Multiplier With Low Space Complexity for All Irreducible Trinomials Over $GF(2^{n})$
Young In Cho, Nam Su Chang, Chang Han Kim, Young-Ho Park, Seokhie Hong · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2011
Koç and Sunar proposed an architecture of the Mastrovito multiplier for the irreducible trinomial$f(x)=x^{n}+x^{k}+1$, where$k eq n/2$to reduce the time complexity. Also, many multipliers based on the Karatsuba-Ofman algorithm (KOA) was proposed that sacrificed time efficiency for low space complexity. In this paper, a new multiplication formula which is a variant of KOA presented. We also provide a straightforward architecture of a non-pipelined bit-parallel multiplier using the new formula. The proposed multiplier has lower space complexity than and comparable time complexity to previous Mastrovito multipliers' for all irreducible trinomials.