|
Abstract : |
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 o function in the input size, total degree, and binary coefficient length for the usual coefficient fields and utputs a straight-line program, which with controllably high probability correctly determines the e c 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 l t straight-line program into its sparse representation. This conversion algorithm is in random-polynomia ime in the previously cited parameters and in an upper bound for the number of non-zero monomials, |
