Hart, William B., van Hoeij, Mark and Novocin, Andrew (2011) Practical polynomial factoring in polynomial time. In: ISSAC '11 International Symposium on Symbolic and Algebraic Computation (co-located with FCRC 2011), San Jose, CA, 7-11 Jun 2011. Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation pp. 163-170.

Full text not available from this repository.

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
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. 163-170
Identification Number:	10.1145/1993886.1993914
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	ISSAC '11 International Symposium on Symbolic and Algebraic Computation (co-located with FCRC 2011)
Type of Event:	Conference
Location of Event:	San Jose, CA
Date(s) of Event:	7-11 Jun 2011
URI:	http://wrap.warwick.ac.uk/id/eprint/43600

Request changes to a record

Actions (login required)

View Item