TY - JOUR

T1 - Complexity of OM factorizations of polynomials over local fields

AU - Bauch, Jens Dietrich

AU - Nart, Enric

AU - Stainsby, Hayden D.

PY - 2013/6/1

Y1 - 2013/6/1

N2 - 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).

AB - 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).

U2 - https://doi.org/10.1112/S1461157013000089

DO - https://doi.org/10.1112/S1461157013000089

M3 - Article

VL - 16

SP - 139

EP - 171

JO - LMS Journal of Computation and Mathematics

JF - LMS Journal of Computation and Mathematics

SN - 1461-1570

ER -