Complexity of OM factorizations of polynomials over local fields
Jens-Dietrich Bauch, Enric Nart, Hayden D. Stainsby · LMS Journal of Computation and Mathematics · 2013
Abstract Let $k$ be a locally compact complete field with respect to a discrete valuation $v$ . Let $ \mathcal{O} $ be the valuation ring, $\mathfrak{m}$ the maximal ideal and $F(x)\in \mathcal{O} [x] $ a monic separable polynomial of degree $n$ . Let $\delta = v(\mathrm{Disc} (F))$ . The Montes algorithm computes an OM factorization of $F$ . The single-factor lifting algorithm derives from this data a factorization of $F(\mathrm{mod~} {\mathfrak{m}}^{ u } )$ , for a prescribed precision $ u $ . 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} { u }^{1+ \epsilon } )$ word operations for the complexity of the computation of a factorization of $F(\mathrm{mod~} {\mathfrak{m}}^{ u } )$ , assuming that the residue field of $k$ is small.