Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T17:20:47.444Z Has data issue: false hasContentIssue false

Complexity of OM factorizations of polynomials over local fields

Published online by Cambridge University Press:  01 June 2013

Jens-Dietrich Bauch
Affiliation:
Departament de Matemàtiques, Universitat Autònoma de Barcelona, Edifici C, E-08193 Bellaterra, Barcelona, Catalonia, Spain email bauch@mat.uab.cat nart@mat.uab.cat hds@mat.uab.cat
Enric Nart
Affiliation:
Departament de Matemàtiques, Universitat Autònoma de Barcelona, Edifici C, E-08193 Bellaterra, Barcelona, Catalonia, Spain email bauch@mat.uab.cat nart@mat.uab.cat hds@mat.uab.cat
Hayden D. Stainsby
Affiliation:
Departament de Matemàtiques, Universitat Autònoma de Barcelona, Edifici C, E-08193 Bellaterra, Barcelona, Catalonia, Spain email bauch@mat.uab.cat nart@mat.uab.cat hds@mat.uab.cat

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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}}^{\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(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$ , assuming that the residue field of $k$ is small.

Information

Type
Research Article
Copyright
© The Author(s) 2013