Efficient multiplication of a vector by an MDS matrix with irreducible characteristic polynomial
Resumen
Multiplication of a vector by an MDS matrix is a key process in many fields, such as cryptography. Algorithms for efficient multiplication of a vector by an MDS matrix have been designed to optimize the multiplication process, reducing the computational complexity, which allows for more efficient resource utilization. In this paper, based on previous work by the lead author, a new algorithm for the efficient multiplication of a vector by an MDS matrix with irreducible characteristic polynomial was designed and substantiated. The presented algorithm is based on the multiplication of two polynomials modulo a generator polynomial of a nontrivial linear MDS code [n, k, d] over and in the worst case it is only necessary to store values of the for the multiplication of a vector by an MDS matrix over and values for the multiplication of the vector by the inverse matrix. Multiplying a vector by an m ×m matrix over or by its inverse has a complexity of ,), whereas if the Karatsuba approach and its improvements are used, the complexity is , where for the best known algorithm . So, the complexity of the algorithm is , plus a multiplication in and it is not necessary to explicitly write the matrix or the inverse.
Palabras clave
Texto completo:
PDF (English)Enlaces refback
- No hay ningún enlace refback.
_________________________________________________________________________________________________________
La Universidad de las Ciencias Informáticas (UCI), a través del sello editorial Ediciones Futuro, publica los contenidos de la Revista Cubana de Ciencias Informáticas (RCCI) bajo licencia Creative Commons de tipo Atribución 4.0 Internacional (CC BY 4.0). Esta licencia permite a otros distribuir, mezclar, ajustar y construir a partir de su obra, incluso con fines comerciales, siempre que le sea reconocida la autoría de la creación original. Saber más
_________________________________________________________________________________________________________
![]() | INDEXACIÓN | ||||||||
![]() | ![]() | ![]() | ![]() | ||||||
| |