Geodesic
Efficient matrix multiplication for cryptography with~a companion matrix over $\mathbb{F}_2$
Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 114-117.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $, 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.
Keywords: companion matrix, cryptology.
Mots-clés : matrix multiplication 
@article{PDMA_2023_16_a28,
     author = {S. Pal},
     title = {Efficient matrix multiplication for cryptography with~a companion matrix over $\mathbb{F}_2$},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {114--117},
     publisher = {mathdoc},
     number = {16},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2023_16_a28/}
}
TY  - JOUR
AU  - S. Pal
TI  - Efficient matrix multiplication for cryptography with~a companion matrix over $\mathbb{F}_2$
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2023
SP  - 114
EP  - 117
IS  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2023_16_a28/
LA  - ru
ID  - PDMA_2023_16_a28
ER  - 
%0 Journal Article
%A S. Pal
%T Efficient matrix multiplication for cryptography with~a companion matrix over $\mathbb{F}_2$
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2023
%P 114-117
%N 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2023_16_a28/
%G ru
%F PDMA_2023_16_a28
S. Pal. Efficient matrix multiplication for cryptography with~a companion matrix over $\mathbb{F}_2$. Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 114-117. http://geodesic.mathdoc.fr/item/PDMA_2023_16_a28/

[1] Mahalanobis A., Are matrices useful in public-key cryptography?, Intern. Math. Forum, 8:39 (2013), 1939–1953 | DOI | MR | Zbl

[2] Herstein I. N., Topics in Algebra, 2nd ed., John Wiley Sons, 2006 | MR

[3] Ghorpade S. R. and Ram S., “Block companion Singer cycles, primitive recursive vector sequences and coprime polynomial pairs over finite fields”, Finite Fields Their Appl., 17:5 (2011), 461–472 | DOI | MR | Zbl