{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:55:16Z","timestamp":1776844516819,"version":"3.51.2"},"reference-count":21,"publisher":"American Mathematical Society (AMS)","issue":"254","license":[{"start":{"date-parts":[[2007,1,3]],"date-time":"2007-01-03T00:00:00Z","timestamp":1167782400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>Popularized by Zassenhaus in the seventies, several algorithms for factoring polynomials use a so-called lifting and recombination scheme. Concerning bivariate polynomials, we present a new algorithm for the recombination stage that requires a lifting up to precision twice the total degree of the polynomial to be factored. Its cost is dominated by the computation of reduced echelon solution bases of linear systems. We show that our bound on precision is asymptotically optimal.<\/p>","DOI":"10.1090\/s0025-5718-06-01810-2","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T11:05:20Z","timestamp":1140001520000},"page":"921-933","source":"Crossref","is-referenced-by-count":18,"title":["Sharp precision in Hensel lifting for bivariate polynomial factorization"],"prefix":"10.1090","volume":"75","author":[{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2006,1,3]]},"reference":[{"key":"1","unstructured":"K. Belabas, M. van Hoeij, J. Kl\u00fcners, and A. Steel, Factoring polynomials over global fields, Manuscript, October 2004."},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/1005285.1005294","article-title":"Complexity issues in bivariate polynomial factorization","author":"Bostan, A.","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/158113827X"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1006\/jabr.2000.8586","article-title":"Absolute irreducibility of polynomials via Newton polytopes","volume":"237","author":"Gao, Shuhong","year":"2001","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"S. Gao, Absolute irreducibility of polynomials via Newton polytopes, J. Algebra 237 (2001), no. 2, 501\u2013520.","DOI":"10.1006\/jabr.2000.8586"},{"issue":"242","key":"5","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1090\/S0025-5718-02-01428-X","article-title":"Factoring multivariate polynomials via partial differential equations","volume":"72","author":"Gao, Shuhong","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"240","key":"6","doi-asserted-by":"publisher","first-page":"1663","DOI":"10.1090\/S0025-5718-01-01393-X","article-title":"Hensel lifting and bivariate polynomial factorisation over finite fields","volume":"71","author":"Gao, Shuhong","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0521826462","edition":"2"},{"key":"8","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, Polynomial factorization: A success story, Proceedings of ISSAC 2003, ACM Press, 2003, pp. 3\u20134.","DOI":"10.1145\/860854.860857"},{"key":"9","unstructured":"G. Lecerf, Improved dense multivariate polynomial factorization algorithms, Manuscript, January 2005."},{"key":"10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1145\/321879.321890","article-title":"Multivariate polynomial factorization","volume":"22","author":"Musser, David R.","year":"1975","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"2","key":"11","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01386831","article-title":"A new efficient factorization algorithm for polynomials over small finite fields","volume":"4","author":"Niederreiter, Harald","year":"1993","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"key":"12","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1515\/crll.1986.369.167","article-title":"Reduzibilit\u00e4t ebener Kurven","volume":"369","author":"Ruppert, Wolfgang","year":"1986","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1006\/jnth.1999.2381","article-title":"Reducibility of polynomials \ud835\udc53(\ud835\udc65,\ud835\udc66) modulo \ud835\udc5d","volume":"77","author":"Ruppert, Wolfgang M.","year":"1999","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF03167271","article-title":"Analysis of approximate factorization algorithm. I","volume":"9","author":"Sasaki, Tateaki","year":"1992","journal-title":"Japan J. Indust. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0916-7005","issn-type":"print"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF03167201","article-title":"A unified method for multivariate polynomial factorizations","volume":"10","author":"Sasaki, Tateaki","year":"1993","journal-title":"Japan J. Indust. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0916-7005","issn-type":"print"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF03167142","article-title":"Approximate factorization of multivariate polynomials and absolute irreducibility testing","volume":"8","author":"Sasaki, Tateaki","year":"1991","journal-title":"Japan J. Indust. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0916-7005","issn-type":"print"},{"key":"17","unstructured":"A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH, Z\u00fcrich, 2000, http:\/\/www.scg.uwaterloo.ca\/\u02dcastorjoh."},{"issue":"134","key":"18","doi-asserted-by":"publisher","first-page":"324","DOI":"10.2307\/2005975","article-title":"Factoring multivariate polynomials over algebraic number fields","volume":"30","author":"Wang, Paul S.","year":"1976","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"19","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1145\/321879.321890","article-title":"Multivariate polynomial factorization","volume":"22","author":"Musser, David R.","year":"1975","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0022-314X(69)90047-X","article-title":"On Hensel factorization. I","volume":"1","author":"Zassenhaus, Hans","year":"1969","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"R. Zippel, Effective polynomial computation, Kluwer Academic Publishers, 1993.","DOI":"10.1007\/978-1-4615-3188-3"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01810-2\/S0025-5718-06-01810-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01810-2\/S0025-5718-06-01810-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:35:36Z","timestamp":1776782136000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01810-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,3]]},"references-count":21,"journal-issue":{"issue":"254","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["S0025-5718-06-01810-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01810-2","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2006,1,3]]}}}