The ShiftlessDecomposition command computes a shiftless decomposition  of f w.r.t. x.

It satisfies the following properties.

  are squarefree and pairwise shift coprime, that is, for  and all integers , we have  if and only if  and

 is constant w.r.t. x, and  are nonconstant primitive polynomials w.r.t. x.

The  and  are non-negative integers with  and  for all .

The shiftless decomposition is unique up to reordering and multiplication by units. The  are ordered by ascending degree in x, but the ordering within the same degree is not determined.

If f is constant w.r.t. x, then the return value is .

Partial factorizations of the input are not taken into account.

Gerhard, J.; Giesbrecht, M.; Storjohann, A.; and Zima, E.V. "Shiftless decomposition and polynomial-time rational summation." Proceedings International Symposium on Symbolic and Algebraic Computation, pp. 119-126. ed. J.R. Sendra. 2003.