Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSingle-factor lifting and factorization of polynomials over local fields
Author(s) Jordi Guàrdia, Enric Nart, Sebastian Pauli
TypeArticle in Journal
AbstractLet f ( x ) be a separable polynomial over a local field. The Montes algorithm computes certain approximations to the different irreducible factors of f ( x ) , with strong arithmetic properties. In this paper, we develop an algorithm to improve any one of these approximations, till a prescribed precision is attained. The most natural application of this “single-factor lifting” routine is to combine it with the Montes algorithm to provide a fast polynomial factorization algorithm. Moreover, the single-factor lifting algorithm may be applied as well to accelerate the computational resolution of several global arithmetic problems in which the improvement of an approximation to a single local irreducible factor of a polynomial is required.
KeywordsLocal field, Montes algorithm, Montes approximation, Newton polygon, Okutsu approximation, Polynomial factorization
URL http://www.sciencedirect.com/science/article/pii/S0747717112000363
JournalJournal of Symbolic Computation
Pages1318 - 1346
Translation No
Refereed No