I've just recently learned about the neat algorithm that, given a polynomial $f$ finds (non linear) polynomials $h,g$ such that $$f = g \circ h \quad (1),$$ or decides that there are no such polynomials.
Clearly if $f$ is of prime degree then such decomposition does not exist. What I wonder is
- Are there any other necessary conditions for $f$ to be decomposable as in $(1)$
- Are there any neat applications of this decomposition technique other than sometimes allowing one to find the roots of large polynomial more efficiently?