Complexity of OM factorizations of polynomials over local fields

2012/04/20 by Bauch, Jens-Dietrich, Nart, Enric, Stainsby, Hayden D. · 1 citation
#11Y40 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1204.4671

Abstract

Let k be a locally compact complete field with respect to a discrete valuation v. Let \oo be the valuation ring, \m the maximal ideal and F(x)∈\oo[x] a monic separable polynomial of degree n. Let δ=v(\dsc(F)). The Montes algorithm computes an OM factorization of F. The single-factor lifting algorithm derives from this data a factorization of F \md\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(n^2+ε+n^1+εδ^2+ε+n²ν^1+ε) word operations for the complexity of the computation of a factorization of F \md\m^ν, assuming that the residue field of k is small.

Cited by

• The minimal periodicity for integral bases of pure number fields

Related

• Single-factor lifting and factorization of polynomials over local fields
• Schemes for Deterministic Polynomial Factoring
• Computing the bound of an Ore polynomial. Applications to factorization
• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
• Fast polynomial factorization and modular composition