ABSTRACT
This chapter summarizes the major advances that now make polynomial factoring a fine example of a classical computational question for which efficient and polynomial time algorithms have been designed. In the multivariate case, the number of possible monomial coefficients can grow exponentially with the number of variables. A densely represented, or shortly a dense multivariate polynomial is one where all coefficients are counted towards the input size, even if a large proportion of them is zero. The algorithms just described have polynomial running time in the dense size of the input polynomial. This chapter describes two algorithms with which one can establish that dense multivariate rational polynomials can be factored in polynomial time. The first algorithm splits univariate integer polynomials, and the second reduces the problem of multivariate factoring to univariate factoring. A computational model for evaluating polynomials and rational functions is that by a straight-line program.
