Details:
Title  Lower bounds for decomposable univariate wild polynomials  Author(s)  Joachim von zur Gathen  Type  Article in Journal  Abstract  A univariate polynomial f over a field is decomposable if it is the composition f = g ∘ h of two polynomials g and h whose degree is at least 2. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood. The wild case, where p divides n, is more challenging. We present an efficient algorithm for this case that computes a decomposition, if one exists. It works for most but not all inputs, and provides a reasonable lower bound on the number of decomposable polynomials over a finite field. This is a central ingredient in finding a good approximation to this number.  Keywords  Computer algebra, Wild polynomial decomposition, Finite fields, Combinatorics on polynomials  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717112001411 
Language  English  Journal  Journal of Symbolic Computation  Volume  50  Number  0  Pages  409  430  Year  2013  Edition  0  Translation 
No  Refereed 
No 
