Fast operations on linearized polynomials and their applications in coding theory. (November 2018)

• Record Type: Journal Article
• Authors: Puchinger, Sven; Wachter-Zeh, Antonia
• Is Part Of: Journal of symbolic computation. Volume 89(2018)
• Page Start: 194
• Page End: 215
• Publication Date: 2018-11
• Subjects: Linearized polynomials -- Skew polynomials -- Fast multiplication -- Fast multi-point evaluation -- Fast minimal subspace polynomial -- Fast decoding; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.11.012
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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.