The Library
Practical polynomial factoring in polynomial time
Tools
Hart, William B., Hoeij, Mark van and Novocin, Andrew, 1983 (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 
Date:  2011 
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 [2] J. Abbott, V. Shoup and P. Zimmermann, Factorization in Z[x]: The Searching Phase, ISSAC'2000 Proceedings, 1{7 (2000). [3] M. Ajtai The shortest vector problem in L2 is NPhard for randomized reductions, STOC 1998, pp. 10{19. [4] K. Belabas A relative van Hoeij algorithm over number fields, J. Symb. Comp. 37 2004, pp. 641{668. [5] K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields, preprint arXiv:math/0409510v1 (2004). [6] J. J. Cannon, W. Bosma (Eds.) Handbook of Magma Functions, Edition 2.13 (2006) [7] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999. [8] W. Hart FLINT, opensource Clibrary. http://www.flintlib.org [9] W. Hart, M. van Hoeij, A. Novocin, Complexity analysis of factoring polynomials, workinprogress, http://andy.novocin.com/pro/complexity.pdf [10] M. van Hoeij, Factoring polynomials and the knapsack problem, J. Num. The., 95 2002, pp. 167{189. [11] M. van Hoeij and A. Novocin, Gradual sublattice reduction and a new complexity for factoring polynomials, accepted for proceedings of LATIN 2010. [12] E. Kaltofen, Polynomial factorization. In: Computer Algebra, 2nd ed "editors B. Buchberger et all, Springer Verlag, 95{113 (1982). [13] E. Kaltofen,On the complexity of finding short vectors in integer lattices, EUROCAL'83,LNCSv.162,pp.235{244 [14] E. Kaltofen, D.R. Musser, and B.D. Saunders A generalized class of polynomials that are hard to factor, SIAM J. Comput.,12(2),pp.473{485 (1983). [15] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 1982, pp. 515{534. [16] L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM 1986 [17] I. Morel, D. Stehlé, and G. Villard, HLLL: Using Householder Inside LLL, ISSAC'09, pp. 271{278. [18] P. Nguyen and D. Stehlé, Floatingpoint LLL revisited, Eurocrypt 2005, v. 3494 LNCS, pp. 215{233. [19] P. Nguyen and D. Stehlé, LLL on the Average, ANTS VII 2006, v. 4076 LNCS, pp. 238{256. [20] A. Novocin, Factoring Univariate Polynomials over the Rationals, Ph.D. Thesis Flor. St. Univ. 2008, http://andy.novocin.com/pro/dissertation.pdf. [21] C. P. Schnorr, A more efficient algorithm for lattice basis reduction, J. of Algo. 9 1988, pp. 47{62. [22] A. Schönhage, Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm, ICALP'84, LNCS 172, pp. 436{447. [23] V. Shoup NTL, opensource C++ library. http://www.shoup.net/ntl/ [24] W. Stein SAGE Mathematics Software. http://www.sagemath.org [25] A. Storjohann, Faster algorithms for integer lattice basis reduction, Technical report 1996, ETH Zürich. [26] H. Zassenhaus, On Hensel factorization I, Journal of Number Theory (1969), pp. 291{311. 
URI:  http://wrap.warwick.ac.uk/id/eprint/43600 
Actions (login required)
View Item 