**MSC:**- 11Y05

]$ 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.