JavaScript is disabled for your browser. Some features of this site may not work without it.
Polynomial Decomposition Algorithms

Author
Kozen, Dexter; Landau, Susan
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.
Date Issued
1986-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-773
Type
technical report