Efficient multiplication of a vector by a matrix MDS

Authors

  • Pablo Freyre Arrozarena
  • Ernesto Dominguez Fiallo

DOI:

https://doi.org/10.54654/isj.v3i17.888

Keywords:

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.

Downloads

Download data is not yet available.

References

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.

Downloads

Abstract views: 84 / PDF downloads: 26

Published

2023-04-01

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

Issue

Section

Papers

Most read articles by the same author(s)