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 $\widetilde 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 and is quasi-optimal in view of the lower bound of Chen–Ye. The proof reduces the finite-field case to the split algebra case using the equivariant multiplication theory of Couveignes–Ezome, and then applies existing fast algorithms.
