Polynomial Factorization Over Henselian Fields

We present an algorithm that, given an irreducible polynomial g over a general valued field (K, v), finds the factorization of g over the Henselianization of K under certain conditions. The analysis leading to the algorithm follows the footsteps of Ore, Mac Lane, Okutsu, Montes, Vaquié and Herrera–Olalla–Mahboub–Spivakovsky, whose work we review in our context. The correctness is based on a key new result (Theorem 4.10), exhibiting relations between generalized Newton polygons and factorization in the context of an arbitrary valuation. This allows us to develop a polynomial factorization algorithm and an irreducibility test that go beyond the classical discrete, rank-one case. These foundational results may find applications for various computational tasks involved in arithmetic of function fields, desingularization of hypersurfaces, multivariate Puiseux series or valuation theory.