2015/04/29 by Narayanan, Anand Kumar
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1504.07697
We propose and rigorously analyze two randomized algorithms to factor univariate polynomials over finite fields using rank 2 Drinfeld modules. The first algorithm estimates the degree of an irreducible factor of a polynomial from Euler-Poincare characteristics of random Drinfeld modules. Knowledge of a factor degree allows one to rapidly extract all factors of that degree. As a consequence, the problem of factoring polynomials over finite fields in time nearly linear in the degree is reduced to finding Euler-Poincare characteristics of random Drinfeld modules with high probability. Notably, the worst case complexity of polynomial factorization over finite fields is reduced to the average case complexity of a problem concerning Drinfeld modules. The second algorithm is a random Drinfeld module analogue of Berlekamp's algorithm. During the course of its analysis, we prove a new bound on degree distributions in factorization patterns of polynomials over finite fields in certain short intervals.