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).
UR - https://www.scopus.com/pages/publications/84880231539
U2 - 10.1112/S1461157013000089
DO - 10.1112/S1461157013000089
M3 - Article
SN - 1461-1570
VL - 16
SP - 139
EP - 171
JO - LMS Journal of Computation and Mathematics
JF - LMS Journal of Computation and Mathematics
ER -