single-factor hensel lifting and its application to the straight-line complexity of certain polynomials
Three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given by straight-line programs of unbounded input degree. The first theorem shows how to compute a higher order partial derivative in a single variable. The other two theorems impose the degree of the output polynomial as a parameter of the length of the output program. First it is shown that if a straight-line program computes an arbitrary power of a multivariate polynomial, that polynomial also admits a polynomial bounded straight-line computation. Second, any factor of a multivariate polynomial given by a division-free straight-line program with relatively prime co-factor also admits a straight-line computation of length polynomial in the input length and the degree of the factor. This result is based on a new Hensel lifting process, one where only one factor image is lifted back to the original factor. As an application we get that the greatest common divisor of polynomials given by a division-free straight-line program has polynomial straight-line complexity in terms of the input length and its own degree.
factor applications complexity polynomial operability program input computation order variability power process image