Factorization of Polynomials Given by Straight-Line Programs.
Erich Kaltofen · 1989
An algorithm is developed for the factorization of a multivariate polynomial represented by traight-line program into its irreducible factors. The algorithm is in random polynomial-time as a function in the input size, total degree, and binary coefficient length for the usual coefficient fields and outputs a straight-line program, which with controllably high probability correctly determines the irreducible factors. It also returns the probably correct multiplicities of each distinct factor. If th oefficient field has finite characteristic p and p divides the multiplicities of some irreducible factors our algorithm constructs straight-line programs for the appropriate p-th powers of such factors. Also a probabilistic algorithm is presented that allows to convert a polynomial given by a straight-line program into its sparse representation. This conversion algorithm is in random-polynomial time in the previously cited parameters and in an upper bound for the number of non-zero...