Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6613
Title: Polynomial Decomposition Algorithms
Authors: Kozen, Dexter
Landau, Susan
Keywords: computer science
technical report
Issue Date: Aug-1986
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-773
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.
URI: http://hdl.handle.net/1813/6613
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
86-773.pdf997.23 kBAdobe PDFView/Open
86-773.ps224.57 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us