Polynomial decomposition algorithms (Q5893804)

A polynomial \(f\) over a commutative ring is said to be decomposable if it has a non-trivial functional decomposition \(f=g\circ h\). Previous algorithms to check decomposability were exponential-time in the worst case and only worked over fields of characteristic 0. The present author describes an \(O(n^2r)\)-algorithm, where \(n\) and \(r\) are degrees of \(f\) and \(g\). The algorithm works over arbitrary commutative rings.