Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleLower bounds for decomposable univariate wild polynomials
Author(s) Joachim von zur Gathen
TypeArticle in Journal
AbstractA 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.
KeywordsComputer algebra, Wild polynomial decomposition, Finite fields, Combinatorics on polynomials
URL http://www.sciencedirect.com/science/article/pii/S0747717112001411
JournalJournal of Symbolic Computation
Pages409 - 430
Translation No
Refereed No