Explicit formulae for Mastrovito matrix and its corresponding Toeplitz matrix for all irreducible pentanomials using shifted polynomial basis

摘要

We propose explicit formulae of the Mastrovito matrix M and its corresponding Toeplitz matrix T for an arbitrary irreducible pentanomial using shifted polynomial basis. We also give the complexity of the Toeplitz matrix for a pentanomial. This yields the complexity of a multiplier based on Toeplitz matrix vector product (TMVP) for an arbitrary irreducible pentanomial for the first time. Moreover, we introduce a new type of pentanomials for which a multiplier based on TMVP is efficiently implemented. We show that the complexity of a subquadratic space complexity multiplier for such a special type of pentanomials is comparable with that for trinomials. (C) 2015 Elsevier B.V. All rights reserved.