Fast Operations on Linearized Polynomials and their Applications in Coding Theory

Sven Puchinger, Antonia Wachter-Zeh

TL;DR

This paper introduces significantly faster algorithms for fundamental operations on linearized polynomials, achieving sub-quadratic complexity in the polynomial degree. These advancements lead to the first sub-quadratic decoding algorithms for Gabidulin codes, a crucial class of error-correcting codes.

What Problem Does This Paper Address?

Linearized polynomials are a fundamental algebraic structure with wide-ranging applications, particularly in coding theory for constructing codes like Gabidulin codes. Efficiently performing operations such as multiplication, division, and evaluation on these polynomials is critical for the performance of decoding algorithms. Previous methods for these operations often had quadratic or higher complexity with respect to the polynomial degree, which became a bottleneck for practical applications. This paper aims to overcome this limitation by developing new algorithms that are sub-quadratic in the polynomial degree, thereby accelerating computations and enabling faster decoding of important error-correcting codes.

Methods

The authors introduce several novel algorithmic techniques:

  • Fast Multiplication for Skew Polynomials: They generalize a fragmentation-based multiplication algorithm for linearized polynomials to skew polynomials. This new algorithm achieves sub-quadratic complexity in the polynomial degree ($s$), independent of the field extension degree ($m$).
  • Sub-quadratic Division: By leveraging the fast multiplication algorithm and a result from Caruso and Le Borgne (2017), they derive a sub-quadratic division algorithm for linearized polynomials.
  • Accelerated q-transform, MSP, MPE, and Interpolation: They develop new divide-and-conquer algorithms for the q-transform, minimal subspace polynomial (MSP) computation, multi-point evaluation (MPE), and interpolation. These algorithms recursively call each other, enabling them to achieve sub-quadratic complexity, often dominated by the fast multiplication or matrix multiplication.
  • Matrix Multiplication Connection: They establish a connection between linearized polynomial multiplication and matrix multiplication over finite fields, particularly when elliptic normal bases exist. This allows them to derive a lower bound on the cost of linearized polynomial multiplication and show its optimality for the case $s=m$.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Sub-quadratic is Achievable: The paper demonstrates that operations on linearized polynomials, previously thought to require at least quadratic time, can indeed be performed in sub-quadratic time with respect to the polynomial degree.
  • Interdependence of Operations: The authors highlight how advancements in one operation (e.g., multiplication) can directly lead to improvements in others (e.g., division), showcasing a synergistic effect.
  • Recursive Algorithms for MSP and MPE: The novel approach of using mutually recursive algorithms for computing minimal subspace polynomials and multi-point evaluations is a key insight, overcoming challenges posed by the non-commutative nature of linearized polynomial multiplication.
  • Gabidulin Code Decoding Breakthrough: The most significant impact is the development of the first sub-quadratic decoding algorithms for Gabidulin codes, which are vital for applications in network coding, cryptography, and distributed storage.

Key Results

  • Multiplication Complexity: A new multiplication algorithm for skew polynomials with complexity $O(s^{\min\{\omega, 1.635\}})$, where $\omega$ is the matrix multiplication exponent.
  • Division Complexity: A sub-quadratic division algorithm with complexity $O(s^{\min\{\omega, 1.635\}} \log s)$.
  • q-transform Complexity: A quasi-linear time algorithm for the q-transform and its inverse, $O(s \log^2(s) \log(\log(s)))$.
  • MSP and MPE Complexity: Algorithms for computing minimal subspace polynomials and multi-point evaluations with complexity $O(s^{\max\{\log_2(3), \min\{\omega, 1.635\}\}} \log(s))$.
  • Interpolation Complexity: A fast interpolation algorithm with complexity $O(s^{\max\{\log_2(3), \min\{\omega, 1.635\}\}} \log(s))$.
  • Gabidulin Code Decoding: The first sub-quadratic decoding algorithms for Gabidulin codes (both error-only and error-erasure) with complexity $O(n^{\max\{\log_2(3), \min\{\omega, 1.635\}\}} \log^2(n))$, where $n$ is the code length.

Limitations and Future Work

  • Field Dependence: While the algorithms are sub-quadratic in the polynomial degree $s$, their complexity still depends on the field extension degree $m$ in some cases, particularly for the q-transform. The authors note that their multiplication algorithm is faster than known ones when $s \leq m$.
  • Elliptic Normal Bases: The optimal multiplication algorithm for $s=m$ relies on the existence of elliptic normal bases, which are not guaranteed for all field extensions.
  • Future Work: The authors suggest extending their work to the study of fast erasure decoding of Gabidulin codes, as initiated by Bohaczuk Venturelli and Silva (2014). They also note that their algorithms can yield practical speed-ups beyond asymptotic improvements by leveraging efficient linear algebra libraries.

Summary updated

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 \leq 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.
BibTeX
@article{puchinger2018fast,
  author = {Sven Puchinger and Antonia Wachter-Zeh},
  title = {{Fast Operations on Linearized Polynomials and their Applications in Coding Theory}},
  journal = {J. Symb. Comput.},
  year = {2018},
  doi = {10.1016/j.jsc.2017.11.012},
}

Loading related content...

Figure