Fast Operations on Linearized Polynomials and their Applications in Coding Theory
Fast Operations on Linearized Polynomials and their Applications in Coding Theory
复制标题
DOI：
10.1016/j.jsc.2017.11.012
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
S. Puchinger;A. Wachter-Zeh
中科院分区：
文献类型：
--
作者：
S. Puchinger;A. Wachter-Zeh
本文考虑线性化多项式运算的快速算法。我们提出了一个新的乘法算法的斜多项式（线性化多项式的推广），具有次二次的复杂性的多项式次数s，独立于底层的字段扩展度m。我们证明了当s≤ m时，我们的乘法算法比所有已知的算法都要快.使用Caruso和Le Borgne（2017）的结果，这立即意味着对于任意多项式次数s的线性化多项式的次二次除法算法。此外，我们提出了次二次复杂度的q变换，多点评价，计算最小子空间多项式，插值，其实现至少是二次之前的算法。使用新的快速算法的q-变换，我们展示了如何在有限域上的矩阵乘法可以通过乘以线性多项式的程度最多S= M，如果存在一个椭圆形的正常基础的扩展度m，提供了一个下界的成本后一个问题。最后，它示出了如何新的快速操作的线性化多项式导致的第一错误和擦除译码算法的Gabidulin码次二次复杂度。
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.