{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:40:36Z","timestamp":1776728436221,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"240","license":[{"start":{"date-parts":[[2002,12,5]],"date-time":"2002-12-05T00:00:00Z","timestamp":1039046400000},"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>This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials.<\/p>","DOI":"10.1090\/s0025-5718-01-01393-x","type":"journal-article","created":{"date-parts":[[2002,9,20]],"date-time":"2002-09-20T14:12:48Z","timestamp":1032531168000},"page":"1663-1676","source":"Crossref","is-referenced-by-count":22,"title":["Hensel lifting and bivariate polynomial factorisation over finite fields"],"prefix":"10.1090","volume":"71","author":[{"given":"Shuhong","family":"Gao","sequence":"first","affiliation":[]},{"given":"Alan","family":"Lauder","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2001,12,5]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321662.321664","article-title":"On Euclid\u2019s algorithm and the computation of polynomial greatest common divisors","volume":"18","author":"Brown, W. S.","year":"1971","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"7","key":"2","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor, David G.","year":"1991","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","unstructured":"L. Carlitz, \u201cThe arithmetic of polynomials in a Galois field\u201d, Amer. J. Math. 54 (1932), 39\u201350.","DOI":"10.2307\/2371075"},{"key":"4","isbn-type":"print","first-page":"317","article-title":"Factoring univariate integral polynomials in polynomial average time","author":"Collins, George E.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/3540095195"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-61440-0_131","article-title":"Random polynomials and polynomial factorization","author":"Flajolet, Philippe","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540614400"},{"key":"6","doi-asserted-by":"crossref","unstructured":"S. Gao, \u201cAbsolute irreducibility of polynomials via Newton polytopes,\u201d J. Algebra 237 (2001), 501\u2013520. (Available at URL: http:\/\/www.math.clemson.edu\/faculty\/Gao)","DOI":"10.1006\/jabr.2000.8586"},{"key":"7","doi-asserted-by":"crossref","unstructured":"S. Gao and A. G. B. Lauder, \u201cDecomposition of polytopes and polynomials,\u201d Discrete and Computational Geometry. 26 (2001), 89\u2013104. (Available at URL: http:\/\/www.math. clemson.edu\/faculty\/Gao)","DOI":"10.1007\/s00454-001-0024-0"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/b102438","volume-title":"Algorithms for computer algebra","author":"Geddes, K. O.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0792392590"},{"issue":"223","key":"10","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1090\/S0025-5718-98-00944-2","article-title":"Subquadratic-time factoring of polynomials over finite fields","volume":"67","author":"Kaltofen, Erich","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"11","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":"12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"190","key":"13","doi-asserted-by":"publisher","first-page":"755","DOI":"10.2307\/2008511","article-title":"Factoring multivariate polynomials over large finite fields","volume":"54","author":"Wan, Da Qing","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"134","key":"14","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":"15","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":"16","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"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-01-01393-X\/S0025-5718-01-01393-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-01-01393-X\/S0025-5718-01-01393-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:04:16Z","timestamp":1776726256000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-01-01393-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12,5]]},"references-count":16,"journal-issue":{"issue":"240","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0025-5718-01-01393-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-01-01393-x","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":[[2001,12,5]]}}}