Efficient multiplication of a vector by an MDS matrix with irreducible characteristic polynomial

Pablo Freyre Arrozarena, Oristela Cuellar Justiz, Ramsés Rodríguez Aulet, Alejandro Freyre Echevarría

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


non-singular matrices; multiplication of polynomials; inverse matrix; characteristic polynomial.

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