Efficient multiplication of a vector by a matrix MDS
DOI:
https://doi.org/10.54654/isj.v3i17.888Keywords:
MDS matrices, multiplication of polynomialsTó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
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
Published
How to Cite
Issue
Section
License
Proposed Policy for Journals That Offer Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Proposed Policy for Journals That Offer Delayed Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
