Polynomial Decomposition Algorithms

Abstract

In a recent paper [BZ], Barton and Zippel examine the question of when a polynomial $f(x)$ over a field of characteristic 0 has a nontrivial decomposition $f(x)=g(h(x))$. They give two exponential-time algorithms, both of which require polynomial factorization. We present an $O(s^{2}r\logr)$ algorithm, where $r$=deg $g$ and $s$ =deg $h$. The algorithm does not use polynomial factorization. We also show that the problem is in $NC$. In addition, we give a new structure theorem for testing decomposibility over any field. We apply this theorem to obtain an $NC$ algorithm for decomposing irreducible polynomials over finite fields and a subexponential algorithm for decomposing irreducible polynomials over any field.