Efficient matrix multiplication for cryptography with a companion matrix over $\mathbb{F}_2$

A number of schemes in cryptography and other allied areas require operations on matrices that are computationally expensive. However, the computational load due to standard operations like multiplication can be drastically reduced by the choice of special matrices. One such special matrix is the companion matrix of a monic polynomial of degree $n$ over a finite field. Due to its cyclic structure and sparseness property, such a matrix not only helps us to reduce the complexity of matrix multiplication but also can be applied for cryptographic purposes. In this paper, an algorithm is proposed for the multiplication of an arbitrary matrix with a companion matrix over a finite field of order $p$. In our algorithm, we not only reduce the complexity but also minimize the number of multiplication operations as much as possible. The complexity of multiplication of any $n \times n$ matrix with a companion matrix of a monic polynomial of degree $n$ is $\mathcal{O}(n^2)$, whereas the complexity of standard matrix multiplication is $\mathcal{O}(n^3)$. Moreover, the number of multiplication operations is $n^2-nt$, $0 \leq t <n$, and $0$ for the fields $\mathbb{F}_p$ and $\mathbb{F}_2$ of order $p$ and $2$, respectively, which is far less than $n^3$ multiplications required for standard matrix multiplication.