Single-factor lifting and factorization of polynomials over local fields

Jordi Guàrdia, Enric Nart, Sebastian Pauli

Research output: Contribution to journalArticleResearchpeer-review

18 Citations (Scopus)

Abstract

Let . 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. © 2012 Elsevier Ltd.
Original languageEnglish
Pages (from-to)1318-1346
JournalJournal of Symbolic Computation
Volume47
Issue number11
DOIs
Publication statusPublished - 1 Nov 2012

Keywords

  • Local field
  • Montes algorithm
  • Montes approximation
  • Newton polygon
  • Okutsu approximation
  • Polynomial factorization

Fingerprint

Dive into the research topics of 'Single-factor lifting and factorization of polynomials over local fields'. Together they form a unique fingerprint.

Cite this