Polynomial-time factoring polynomials over local fields

A. L. Chistov

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 112-148

Résumé

An algorithm is constructed for factoring multivariable polynomials over local fields with complexity polynomial in the size of input data and characteristic $p$ of the residue field of the local field. All earlier known algorithms even for the case of one variable required an enumeration exponential in the degree of the polynomial under factorization before applying Hensel's lemma. Elements of local fields are represented as sums of power series in the uniformizing element with coefficients in the system of representatives of the residue field. We set by definition that a series is computed within time polynomial in $A_1,\dots,A_m$ iff its $i$-th partial sum is computed within time polynomial in $A_1,\dots,A_m$ and $i$ for each $i$. The polynomial in input has coefficients in a global field. The algorithm uses Newton's polygon method for constructing roots of a polynomial in one variable. However in its classical form, as in the case when the residue field has zero characteristic this method does not succeed because of the existence of higher ramification for extensions of local fields when one can not choose in advance a uniformizing element in the extension. To solve the problem we use a decomposition of a special kind in the quotient algebra modulo a polynomial under factoring. It is constructed additionally within polynomial time uniformizing elements and residue fields of extensions of the input local field by a root of the polynomial factored. In the case of nonzero characteristic, an analog of our algorithm is the classical algorithm for resolution of singularities of algebraic curves over finite fields. Thus, our algorithm can be regarded as a new efficient method for local resolution of singularities in rings which are finite over $\mathbb{Z}$ or $\mathbb{F}_p[t]$. In short form this result was published in “Soviet Math. Dokl.”, Vol. 35 (1987), No 2.