Factoring rational polynomials over the complex numbers. (English) Zbl 0772.12001

The paper describes algorithms which are in NC, for determining the number and the degrees of the factors, irreducible over \(\mathbb{C}\), of a multivariate polynomial with coefficients in \(\mathbb{Q}\) and for approximating the irreducible factors. (NC is the class of functions which are computable by logspace-uniform Boolean circuits of polynomial size and of polylogarithmic depth.) The measures of size of the input polynomial are its degree, the coefficient length and the number \(n\) of variables. For fixed \(n\) a deterministic NC algorithm is given; if \(n\) is not fixed the algorithm to find the number and the degrees of the irreducible factors is random NC.
To determine the number of irreducible factors the general case is reduced (via Bertini’s theorem) to the case of a squarefree polynomial in two variables, and in this case the number of irreducible factors is determined by calculating the connectivity of a suitably constructed graph, using Sturm sequences. The approximation of the irreducible factors is based on a result of C. A. Neff [Proc. 31st Ann. Sympos. Found. Comput. Sci., 152-162 (1990)] on finding zeros of polynomials in one variable in NC.


12D05 Polynomials in real and complex fields: factorization
12Y05 Computational aspects of field theory and polynomials (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link