Factoring Rational Polynomials over the Complex Numbers

We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multivariate polynomial with rational coefficients. NC is the class of functions computable by logspace-uniform boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polyne mial are its degree d, coefficient length c, number of variables ra, and for sparse polynomials, the number of non-zero coefficients s. For the general case, we give a random (Monte-Carlo) NC algorithm in these input measures. If n is fixed, or if the polynomial is dense, we give a deterministic NC algorithm. The algorithm also works in random NC for polynomials represented by straight-line programs, provided the polynomial can be evaluated at integer points in NC. Finally, we discuss a method for obtaining an approximation to the coefficients of each factor whose running time is polynomial in the size of the original (dense) polynomial. These methods rely on the fact that the connected components of a complex hypersurface P(zl,..., zn) = 0 minus its singular points correspond to the absolute factors of P.