Complexity of Low-Degree Skew Polynomial Multiplication over Finite Fields

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 ${\mathbb{F}}_{q^n}[x;\sigma ]$ of degree at most $d<n$ can be computed using $\tilde{O}(d^{{\omega }_K-1}n)$ arithmetic operations over ${\mathbb{F}}_q$, where $\sigma$ 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.