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 | 0747-7171 |
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 |
|