Efficient multiplier based on hybrid approach for Toeplitz matrix-vector product

We propose a hybrid approach for a Toeplitz matrix-vector product (TMVP) of size k⋅2i3j, where k≥1 and i,j≥0. It is possible to make trade-offs between time and space complexities for a TMVP by choosing values k, i, and j properly. We show that the multiplier based on the proposed hybrid TMVP approach has lower space as well as time complexities than other subquadratic space complexity multipliers for five fields recommended by NIST. Moreover, for those five fields, the space complexities of the proposed multiplier are reduced by a minimum 59% and a maximum 77% compared with quadratic space complexity multiplier.