In mathematics, a **polynomial decomposition** expresses a polynomial *f* as the functional composition of polynomials *g* and *h*, where *g* and *h* have degree greater than 1; it is an algebraic functional decomposition. Algorithms are known for decomposing univariate polynomials in polynomial time.

Polynomials which are decomposable in this way are **composite polynomials**; those which are not are called **indecomposable polynomials** of sometimes **prime polynomials**.^{[1]} (not to be confused with irreducible polynomials, which cannot be factored into products of polynomials).

The rest of this article discusses only univariate polynomials; algorithms also exist for multivariate polynomials of arbitrary degree.^{[2]}

## Examples

In the simplest case, one of the polynomials is a monomial. For example,

decomposes into

since

using the ring operator symbol **∘** to denote function composition.

Less trivially,

## Uniqueness

A polynomial may have distinct decompositions into indecomposable polynomials where where for some . The restriction in the definition to polynomials of degree greater than one excludes the infinitely many decompositions possible with linear polynomials.

Joseph Ritt proved that , and the degrees of the components are the same, but possibly in different order; this is **Ritt's polynomial decomposition theorem**.^{[1]}^{[3]} For example, .

## Applications

A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,

can be calculated with only 3 multiplications using the decomposition, while Horner's method would require 7.

A polynomial decomposition enables calculation of symbolic roots using radicals, even for some irreducible polynomials. This technique is used in many computer algebra systems.^{[4]} For example, using the decomposition

the roots of this irreducible polynomial can be calculated as

- .
^{[5]}

Even in the case of quartic polynomials, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form. For example, the decomposition

gives the roots

^{[5]}

but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand:

- .

## Algorithms

The first algorithm for polynomial decomposition was published in 1985,^{[6]} though it had been discovered in 1976^{[7]} and implemented in the Macsyma computer algebra system.^{[8]} That algorithm takes worst-case exponential time but works independently of the characteristic of the underlying field.

More recent algorithms run in polynomial time but with restrictions on the characteristic.^{[9]}

The most recent algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.^{[10]}

## Notes

- ^
^{a}^{b}J.F. Ritt, "Prime and Composite Polynomials",*Transactions of the American Mathematical Society***23**:1:51–66 (January, 1922) doi:10.2307/1988911 JSTOR 1988911 **^**Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography",*Journal of Symbolic Computation*,**44**:1676-1689 (2009), doi:10.1016/j.jsc.2008.02.005**^**Capi Corrales-Rodrigáñez, "A note on Ritt's theorem on decomposition of polynomials",*Journal of Pure and Applied Algebra***68**:3:293–296 (6 December 1990) doi:10.1016/0022-4049(90)90086-W**^**The examples below were calculated using Maxima.- ^
^{a}^{b}Where each ± is taken independently. **^**David R. Barton, Richard Zippel, "Polynomial Decomposition Algorithms",*Journal of Symbolic Computation***1**:159–168 (1985)**^**Richard Zippel , "Functional Decomposition" (1996) full text**^**Available in its open-source successor, Maxima, see the*polydecomp*function**^**Dexter Kozen, Susan Landau, "Polynomial Decomposition Algorithms",*Journal of Symbolic Computation***7**:445–456 (1989)**^**Raoul Blankertz, "A polynomial time algorithm for computing all minimal decompositions of a polynomial",*ACM Communications in Computer Algebra***48**:1 (Issue 187, March 2014) full text Archived 2015-09-24 at the Wayback Machine

## References

- Joel S. Cohen, "Polynomial Decomposition", Chapter 5 of
*Computer Algebra and Symbolic Computation*, 2003, ISBN 1-56881-159-4