2016/06/02 by Anand Kumar Narayanan, Narayanan, Anand Kumar
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.CC #cs.DS #cs.SC #math.NT
paper · pdf · doi:10.48550/arxiv.1606.00898
arxiv created 2016/06/02 · openalex publication_date 2016/06/02 · arxiv updated 2016/06/06 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We present novel algorithms to factor polynomials over a finite field \Fq of odd characteristic using rank 2 Drinfeld modules with complex multiplication. The main idea is to compute a lift of the Hasse invariant (modulo the polynomial f(x) ∈ \Fq[x] to be factored) with respect to a Drinfeld module ϕ with complex multiplication. Factors of f(x) supported on prime ideals with supersingular reduction at ϕ have vanishing Hasse invariant and can be separated from the rest. A Drinfeld module analogue of Deligne's congruence plays a key role in computing the Hasse invariant lift. We present two algorithms based on this idea. The first algorithm chooses Drinfeld modules with complex multiplication at random and has a quadratic expected run time. The second is a deterministic algorithm with O(√(p)) run time dependence on the characteristic p of \Fq.