Fast operations on linearized polynomials and their applications in coding theory

Sven Puchinger, Antonia Wachter-Zeh

Abstract

This research presents a significant advancement in computational algebra by introducing algorithms that break the "quadratic barrier" for operations on linearized polynomials. By reducing the complexity of multiplication, division, and interpolation to sub-quadratic bounds, the authors enable the first sub-quadratic decoding algorithm for Gabidulin codes, which are essential for network coding and cryptography.

Introduction

Linearized polynomials, or $q$-polynomials, are defined by exponents that are powers of $q$ (e.g., $a_0x^{q^0} + a_1x^{q^1} + \dots$). These structures are fundamental to rank-metric codes, such as Gabidulin codes, which protect data based on matrix rank rather than individual symbol errors. Despite their importance, linearized polynomials present a unique computational challenge: they are non-commutative under composition.

The Computational Challenge

Historically, operations on linearized polynomials have been computationally expensive. Unlike standard polynomials, which benefit from the Fast Fourier Transform (FFT) to achieve quasi-linear complexity, linearized polynomial operations like multi-point evaluation and interpolation have traditionally been limited to quadratic ($O(s^2)$) or cubic ($O(s^3)$) complexity relative to the degree $s$.

Baseline cost bounds for linearized polynomial operations prior to this work.

As data transmission requirements increase, these bottlenecks hinder the practical application of rank-metric codes in real-world scenarios. Most existing implementations for multiplication and evaluation have been unable to scale efficiently with growing polynomial degrees.

Algorithmic Innovations

The authors achieve sub-quadratic speedups by bridging abstract algebra with fast linear algebra. Key techniques include:

  • Polynomial Fragmentation: Utilizing a "baby-steps giant-steps" approach to fragment skew polynomials, allowing multiplication to be transformed into a large matrix multiplication problem.
  • Matrix Multiplication Exponent ($\omega$): By leveraging fast matrix multiplication algorithms with complexity $O(n^\omega)$ (where $\omega < 3$), the authors achieve sub-quadratic bounds.
  • Convoluted Recursion: A divide-and-conquer strategy was developed for Multi-Point Evaluation (MPE) and Minimal Subspace Polynomial (MSP) computation. Due to non-commutativity, the MSP and MPE algorithms are mutually recursive to navigate the polynomial structure.
  • Toeplitz Reduction: The $q$-transform is reduced to a vector-Toeplitz matrix multiplication, enabling quasi-linear performance.

Complexity Improvements

The paper provides a dramatic improvement in asymptotic complexity across all major operations. Notably, the algorithms are sub-quadratic in the polynomial degree $s$ and independent of the field extension degree $m$, making them highly versatile.

Comparison of new sub-quadratic complexity bounds against previous results.

The most impactful result is the achievement of $O(n^{1.635})$ complexity for decoding Gabidulin codes, representing the first sub-quadratic algorithm for this task. This breaks the long-standing $O(n^2)$ barrier for decoding in the rank metric.

Conclusion and Future Work

While these results are theoretically groundbreaking, the authors acknowledge the presence of "hidden constants" associated with fast matrix multiplication. In practice, these algorithms may only outperform naive methods at very high polynomial degrees. Future research will focus on optimized software implementations to identify the practical crossover points and extending these techniques to a broader class of skew polynomials used in symbolic computation.

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