Efficient multiplication of a vector by a matrix MDS


  • Pablo Freyre Arrozarena
  • Ernesto Dominguez Fiallo




MDS matrices, multiplication of polynomials

Tóm tắt

Abstract An algorithm is proposed for the efficient multiplication of a vector by an n x n MDS matrix defined on Fq or by its inverse. The algorithm is based on the multiplication of two polynomials modulo a polynomial of degree n Reed-Solomon code generator and has complexity O(nlog2log2(nlog2q)).

The algorithm only needs to store n values of the Fq field for the multiplication of a vector by an n x n MDS matrix and 2n values for the multiplication of the vector by the inverse matrix.


Download data is not yet available.


Gupta, K. C., Pandey, S. K., and Venkateswarlu, A. “On the direct construction of recursive MDS matrices,” Designs, Codes and Cryptography, 82(1), 77-94, 2017.

Gupta, K. C., Pandey, S. K., and Samanta, S. “Construction of Recursive MDS Matrices Using DLS Matrices,” In International Conference on Cryptology in Africa (pp. 3-27). Springer, Cham, 2022.

J. Alman and V. V. Williams, “A refined laser method and faster matrix multiplication,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021, pp. 522–539.

D. F. Holt, B. Eick, and E. A. O’Brien, “Handbook of computational group theory,” CRC Press, 2005.

Freyre P., Díaz N. and Morgado E., “Some algorithms related to matrices with entries in a finite field,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 12(5), 2009, pp. 509–519.

W. W. Peterson, W. Peterson, E. J. Weldon, and E. J. Weldon, “Error-correcting codes,” MIT press, 1972.


Abstract views: 472 / PDF downloads: 75



How to Cite

Freyre Arrozarena, P. ., & Fiallo, E. D. (2023). Efficient multiplication of a vector by a matrix MDS . Journal of Science and Technology on Information Security, 3(17), 26-36. https://doi.org/10.54654/isj.v3i17.888




Most read articles by the same author(s)