Complexity of Low-Degree Skew Polynomial Multiplication over Finite Fields

2026/07/01 by Ke Ye, Yichuan Cao, Ruichen Qiu · 1 voice
Computer Science · #cs.SC

paper · pdf

Abstract

In this note, we study the complexity of multiplication in skew polynomial rings over finite fields. We prove that the product of two elements in \mathbbF_qⁿ[x;σ] of degree at most d < n can be computed using \widetilde O(d^ω_K-1n) arithmetic operations over \mathbbF_q, where σ is the q-Frobenius automorphism. This matches the conjectural upper bound of Caruso--Le Borgne~[ISSAC'17] and is quasi-optimal in view of the lower bound of Chen--Ye [ISSAC'24]. The proof reduces the finite-field case to the split algebra case using the equivariant multiplication theory of Couveignes--Ezome~[J.~Algebra, 2023], and then applies existing fast algorithms.

Citations

• A quasi-optimal lower bound for skew polynomial multiplication
• The equivariant complexity of multiplication in finite field extensions
• Sub-Quadratic Decoding of Gabidulin Codes
• Fast Operations on Linearized Polynomials and their Applications in Coding Theory
• Skew polynomial rings, Groebner bases and the letterplace embedding of the free associative algebra
• Theory of Non-Commutative Polynomials

Discussions

• Ke Ye, Yichuan Cao, Ruichen Qiu: Complexity of Low-Degree Skew Polynomial Multiplication over Finite Fields https://arxiv.org/abs/2607.00476 https://arxiv.org/pdf/2607.00476 https://arxiv.org/html/260 [bsky, 0 points, 0 comments]

Related

• A quasi-optimal lower bound for skew polynomial multiplication
• Some algorithms for skew polynomials over finite fields
• Faster Polynomial Multiplication via Discrete Fourier Transforms
• Faster polynomial multiplication over finite fields
• Quasi-Optimal Arithmetic for Quaternion Polynomials