On the Characteristic Polynomial of Linearized Polynomials

2025/06/20 by Bastioni, Luca, Micheli, Giacomo, Zhao, Shujun
Computer Science · #11B83 #11T06 #11Y16 #68Q25 #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2506.16937

openalex publication_date 2025/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let k be a finite field, and L be a q-linearized polynomial defined over k of q-degree r (L=∑^r_i=0a_iZ^qi, with a_i∈ k). This paper provides an algorithm to compute a characteristic polynomial of L over a large extension field \mathbb F_qⁿ⊇ k. Our algorithm has computational complexity of O(n(log(n))⁴) 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.

Citations

• Algorithms for computing norms and characteristic polynomials on general Drinfeld modules
• Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology
• Faster Matrix Multiplication via Asymmetric Hashing
• Deterministic computation of the characteristic polynomial in the time\n of matrix multiplication
• A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence

Related

• Linearized polynomials over finite fields revisited
• Linearized polynomial maps over finite fields
• Linearization of polynomials in prime characteristic, with applications to the Golay code and Steiner system
• Semi-characteristic polynomials, ϕ-modules and skew polynomials
• Nilpotent linearized polynomials over finite fields and applications