Multiway Splitting Method for Toeplitz Matrix Vector Product
2012; Institute of Electrical and Electronics Engineers; Volume: 62; Issue: 7 Linguagem: Inglês
10.1109/tc.2012.95
ISSN2326-3814
AutoresM. Anwar Hasan, Christophe Négre,
Tópico(s)Cryptography and Data Security
ResumoComputing the product of a Toeplitz matrix and a vector arises in various applications including cryptography. In this paper, we consider Toeplitz matrices and vectors with entries in $({\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_2)$. For improved efficiency in such computations, large Toeplitz matrices and vectors are recursively split and special formulas with subquadratic arithmetic complexity are applied. To this end, we first present a formula for the five-way splitting and then provide a generalization for the $(k)$-way splitting, where $(k)$ is an arbitrary integer. These formulas can be used to compute a Toeplitz matrix-vector product (TMVP) of size $(n)$ with an arithmetic complexity of $(O(n^{\log_k(k(k+1)/2)}))$.
Referência(s)