2015/12/21 by Sven Puchinger, Puchinger, Sven, Antonia Wachter-Zeh +1
Computer Science · Mathematics · #Advanced Data Storage Technologies #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Information Theory (cs.IT) #Symbolic Computation (cs.SC) #cs.IT #cs.SC #math.IT
paper · pdf · doi:10.48550/arxiv.1512.06520
25 pages, submitted to Journal of Symbolic Computation
openalex publication_date 2015/12/21 · arxiv created 2017/07/11 · arxiv updated 2017/07/12 · openalex created_date 2022/08/18 · openalex updated_date 2026/07/28
This paper considers fast algorithms for operations on linearized polynomials. We propose a new multiplication algorithm for skew polynomials (a generalization of linearized polynomials) which has sub-quadratic complexity in the polynomial degree s, independent of the underlying field extension degree~m. We show that our multiplication algorithm is faster than all known ones when s ≤ m. Using a result by Caruso and Le Borgne (2017), this immediately implies a sub-quadratic division algorithm for linearized polynomials for arbitrary polynomial degree s. Also, we propose algorithms with sub-quadratic complexity for the q-transform, multi-point evaluation, computing minimal subspace polynomials, and interpolation, whose implementations were at least quadratic before. Using the new fast algorithm for the q-transform, we show how matrix multiplication over a finite field can be implemented by multiplying linearized polynomials of degrees at most s=m if an elliptic normal basis of extension degree m exists, providing a lower bound on the cost of the latter problem. Finally, it is shown how the new fast operations on linearized polynomials lead to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity.