On the Characteristic Polynomial of Linearized Polynomials

Abstract

Let $k$ be a finite field, and $L$ be a $q$-linearized polynomial defined over $k$ of $q$-degree $r$ ($L={\sum }_{i=0}^r{a}_i{Z}^{q^i}$, with $a_i\in k$). This paper provides an algorithm to compute a characteristic polynomial of $L$ over a large extension field ${\mathbb{F}}_{q^n}\supseteq k$. Our algorithm has computational complexity of $O(n(\log (n){)}^4)$ in terms of ${\mathbb{F}}_q$ operations with the implied constant depending only on $k$ and $r$. Up to logarithmic factors, and for linear maps represented by low degree polynomials, this provides a square root improvement over generic algorithms.