Efficient Factoring Polynomials over Local Fields and Its Applications
Alexander L. Chistov · 1990
In this paper an algorithm is described for factoring multivariable polynomials over. local fields. The complexity of the algorithm is polynomial in the size of input and the characteristic p of the residue field of the local field. As an application a polynomial equivalence is ascertained for the problem of constructing a basis of the ring of all integers of a given number field and the problem of finding square free part of an integer. It means that the first (respectively second) of these problems can be solved within polynomial time if there is an oracle for solving the second (respectively first) problem within polynomial time. Even the more general result is proved which is also valid in the case of non-zero characteristic, see Theorem 2. In proofs of the last results we use on the one hand the factorization of polynomials over local fields and on the other hand an idea which is applied for obtaining efficient bounds for sizes of coefficients in the Newton-Puiseux expansion, see [8, 7] and also Lemma 1 below. The present results solve in particular problems posed by H.W. Lenstra, Jr. in [9]. In the general case, even for one variable, earlier known algorithms required for factoring polynomials over local fields an enumeration exponential in the size of input data before applying Hensel's lemma, see [1]. Elements of local fields are represented as sums of infinite series. Here and below we regard a series as computable in time polynomial in Ax,.,., Am iff its /th partial sum S{ is computed in time polynomial in Au ..., Am and / for all /. Besides that, if computation of St involves other infinite series, then it should involve a number of initial terms polynomial in iandAl9.,.9Am. Our algorithm of the factorization uses the method of Newton's polygons for constructing roots of polynomials in one variable. However, in its classical form, as in the case when the residue field is of zero characteristic, this method does not succeed because of the presence of higher ramification for exlention of local fields, when one cannot choose in advance a uniformizing element in the extension. For solving the problem we use additionally expansions of a special type in the factor algebra modulo the polynomial under the factorization. Our algorithm is of the greatest interest in the case when the characteristic of the local field is zero. In the case of non-zero characteristic an analog of this algorithm is the classical algorithm