  Let $k$ be a locally compact complete field with respect to a discrete
valuation $v$. Let $\oo$ be the valuation ring, $\m$ the maximal ideal and
$F(x)\in\oo[x]$ a monic separable polynomial of degree $n$. Let
$\delta=v(\dsc(F))$. The Montes algorithm computes an OM factorization of $F$.
The single-factor lifting algorithm derives from this data a factorization of
$F \md{\m^\nu}$, for a prescribed precision $\nu$. In this paper we find a new
estimate for the complexity of the Montes algorithm, leading to an estimation
of $O(n^{2+\epsilon}+n^{1+\epsilon}\delta^{2+\epsilon}+n^2\nu^{1+\epsilon})$
word operations for the complexity of the computation of a factorization of $F
\md{\m^\nu}$, assuming that the residue field of $k$ is small.

Number Theory