Polynomial decomposition algorithms (Q5903274)

\textit{M. Fried} and \textit{R. MacRae} [Math. Ann. 180, 220--226 (1969; Zbl 0185.28803)] proved the following theorem: Let \(f,g,p,q\) be univariate polynomials over an arbitrary field \(k\). Then \(p(x)-q(z)\) divides \(f(x)-g(z)\) if and only if there exists a polynomial \(F(t)\) over \(k\) such that \(f(t)=F(p(t))\) and \(g(t)=F(q(t)).\) The authors present two polynomial decomposition algorithms based on this result (they find a complete decomposition of a polynomial \(f\) in the form \(f=g\circ\dots\circ h\), where \(\circ\) denotes functional composition).