English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper considers fast algorithms for operations on linearizedpolynomials. We propose a new multiplication algorithm for skew polynomials (ageneralization of linearized polynomials) which has sub-quadratic complexity inthe polynomial degree $s$, independent of the underlying field extensiondegree~$m$. We show that our multiplication algorithm is faster than all knownones when $s \leq m$. Using a result by Caruso and Le Borgne (2017), thisimmediately implies a sub-quadratic division algorithm for linearizedpolynomials for arbitrary polynomial degree $s$. Also, we propose algorithmswith sub-quadratic complexity for the $q$-transform, multi-point evaluation,computing minimal subspace polynomials, and interpolation, whoseimplementations were at least quadratic before. Using the new fast algorithmfor the $q$-transform, we show how matrix multiplication over a finite fieldcan be implemented by multiplying linearized polynomials of degrees at most$s=m$ if an elliptic normal basis of extension degree $m$ exists, providing alower bound on the cost of the latter problem. Finally, it is shown how the newfast operations on linearized polynomials lead to the first error and erasuredecoding algorithm for Gabidulin codes with sub-quadratic complexity.

Fast Operations on Linearized Polynomials and their Applications in Coding Theory