Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials

Tong Zhang, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

86 Scopus citations


This paper considers the design of bit-parallel dedicated finite field multipliers using standard basis. An explicit algorithm is proposed for efficient construction of Mastrovito product matrix, based on which we present a systematic design of Mastrovito multiplier applicable to GF(2 m) generated by an arbitrary irreducible polynomial. This design effectively exploits the spatial correlation of elements in Mastrovito product matrix to reduce the complexity. Using a similar methodology, we propose a systematic design of modified Mastrovito multiplier, which is suitable for GF(2 m) generated by high-Hamming weight irreducible polynomials. For both original and modified Mastrovito multipliers, the developed multiplier architectures are highly modular, which is desirable for VLSI hardware implementation. Applying the proposed algorithm and design approach, we study the Mastrovito multipliers for several special irreducible polynomials, such as trinomial and equally-spaced-polynomial, and the obtained complexity results match the best known results. Moreover, we have discovered several new special irreducible polynomials which also lead to low-complexity Mastrovito multipliers.

Original languageEnglish (US)
Pages (from-to)734-749
Number of pages16
JournalIEEE Transactions on Computers
Issue number7
StatePublished - Jul 2001


  • Complexity
  • Finite (or Galois) field
  • Irreducible polynomials
  • Multiplication
  • Standard basis
  • Toeplitz matrix
  • VLSI architecture


Dive into the research topics of 'Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials'. Together they form a unique fingerprint.

Cite this