Mastrovito Multiplier for All Trinomials

B. Sunar and C. K. Koc

IEEE Transactions on Computers, 48(5):522-527, May 1999.

Abstract

An efficient algorithm for the multiplication in GF(2^m) was introduced by Mastrovito. The space complexity of the Mastrovito multiplier for the irreducible trinomial x^m+x+1 was given as m^2-1 XOR and m^2 AND gates. 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^m+x^n+1, where m is not equal to 2n, also requires m^2-1 XOR and m^2 AND gates. However, m^2-m/2 XOR gates are sufficient when the generating trinomial is of the form x^m+x^(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^7+x^4+1 and x^6+x^3+1.