factoring rational polynomials over the complexes
We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multi-variate 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 polynomial are its degree d , coefficient length c , number of variables n , 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 ( z 1 , z n ) = 0 minus its singular points correspond to the absolute factors of P .
factor polynomial complexity algorithm class circuits size measurement input variability general case randomization program point method approximation timing component monte carlo