Complexity of OM factorizations of polynomials over local fields

Details Complexity of OM factorizations of polynomials over local fields Complexity of OM factorizations of polynomials over local fields

2012-04-20

arxiv.org/abs/1204.4671v1

Mathematics

Number Theory

Scientific paper

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)\in\oo[x]$ a monic separable polynomial of degree $n$. Let $\delta=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^\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 \md{\m^\nu}$, assuming that the residue field of $k$ is small.

Affiliated with

Also associated with

No associations

Rating

Complexity of OM factorizations of polynomials over local fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of OM factorizations of polynomials over local fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of OM factorizations of polynomials over local fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6060