Mihailescu Preda
On polynomials in $\F_q[X]$ with abelian lifts and their factorization.
Preprint series: Mathematica Gottingensis
MSC:
11Y05
Abstract: We give a new frame for factorization of polynomials $F(X) \in \F_q[ X
]$ with $\F_q$ a finite field of characteristic $p$, which have equal
degree factorization. Under some additional condition, the dominant
term in the complexity of the factorization then depends on the number
of factors and not on the degree of $F(X)$.

A general class of polynomials satisfying our conditions are the
polynomials \textit{with abelian lift} - i.e. polynomials which arise
as reduction of polynomials defining relative abelian extensions of
number fields, modulo some prime ideal of the base field. We give
details for the special cases of cyclotomic polynomials and cyclic
factors of division polynomials. Even in the case of cyclotomic
polynomials, which is one of the best understood problems in
computational algebra, the gains are noteworthy.

Keywords: Factorization of polynomials (over finite fields) with abelian lifts.