The Library
Practical polynomial factoring in polynomial time
Tools
Hart, William B., Hoeij, Mark van and Novocin, Andrew (2011) Practical polynomial factoring in polynomial time. In: ISSAC '11 International Symposium on Symbolic and Algebraic Computation (colocated with FCRC 2011), San Jose, CA, 711 Jun 2011. Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation pp. 163170.

Text
WRAP_Hart_0584144ma270913poly_factor.pdf  Accepted Version Download (566Kb)  Preview 
Official URL: http://dx.doi.org/10.1145/1993886.1993914
Abstract
State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (less Hensel lifting) for these more common polynomials. In addition, factoring has suffered from a 25 year complexity gap because the best implementations are much faster in practice than their complexity bounds. We illustrate that this complexity gap can be closed by providing an implementation which is comparable to the best current implementations and for which competitive complexity results can be proved.
Item Type:  Conference Item (Paper)  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Mathematics  
Library of Congress Subject Headings (LCSH):  Algorithms  
Journal or Publication Title:  Proceedings of the 36th international symposium on Symbolic and algebraic computation  
Publisher:  ACM  
ISSN:  9781450306751  
Book Title:  Proceedings of the 36th international symposium on Symbolic and algebraic computation  ISSAC '11  
Official Date:  2011  
Dates: 


Page Range:  pp. 163170  
Identification Number:  10.1145/1993886.1993914  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  Engineering and Physical Sciences Research Council (EPSRC) , National Science Foundation (U.S.) (NSF)  
Grant number:  EP/G004870/1 (EPSRC) ; 0728853, 1017880 (NSF)  
Conference Paper Type:  Paper  
Title of Event:  ISSAC '11 International Symposium on Symbolic and Algebraic Computation (colocated with FCRC 2011)  
Type of Event:  Conference  
Location of Event:  San Jose, CA  
Date(s) of Event:  711 Jun 2011  
References:  [1] J. Abbott Bounds on Factors in Z[x] arXiv:0904.3057 

URI:  http://wrap.warwick.ac.uk/id/eprint/43600 
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year