Complexity of OM factorizations of polynomials over local fields

Jens Dietrich Bauch, Enric Nart, Hayden D. Stainsby

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)


Let k be a locally compact complete field with respect to a discrete valuation v. Let O be the valuation ring, m the maximal ideal and F(x)\in O [x] a monic separable polynomial of degree n. Let δ = v(Disc (F)). The Montes algorithm computes an OM factorization of F. The single-factor lifting algorithm derives from this data a factorization of F(mod mν), for a prescribed precision ν . In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of O(n2+ ε + n 1+ ε δ2+ ε +n2μ 1+ ε) word operations for the complexity of the computation of a factorization of F(mν), assuming that the residue field of k is small. © 2013 The Author(s).
Original languageEnglish
Pages (from-to)139-171
JournalLMS Journal of Computation and Mathematics
Publication statusPublished - 1 Jun 2013


Dive into the research topics of 'Complexity of OM factorizations of polynomials over local fields'. Together they form a unique fingerprint.

Cite this