{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:45:08Z","timestamp":1776728708578,"version":"3.51.2"},"reference-count":54,"publisher":"American Mathematical Society (AMS)","issue":"242","license":[{"start":{"date-parts":[[2003,2,28]],"date-time":"2003-02-28T00:00:00Z","timestamp":1046390400000},"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>A new method is presented for factorization of bivariate polynomials over any field of characteristic zero or of relatively large characteristic. It is based on a simple partial differential equation that gives a system of linear equations. As in Berlekamp\u2019s and Niederreiter\u2019s algorithms for factoring univariate polynomials, the dimension of the solution space of the linear system is equal to the number of absolutely irreducible factors of the polynomial to be factored, and any basis for the solution space gives a complete factorization by computing gcd\u2019s and by factoring univariate polynomials over the ground field. The new method finds absolute and rational factorizations simultaneously and is easy to implement for finite fields, local fields, number fields, and the complex number field. The theory of the new method allows an effective Hilbert irreducibility theorem, thus an efficient reduction of polynomials from multivariate to bivariate.<\/p>","DOI":"10.1090\/s0025-5718-02-01428-x","type":"journal-article","created":{"date-parts":[[2003,2,10]],"date-time":"2003-02-10T11:10:52Z","timestamp":1044875452000},"page":"801-822","source":"Crossref","is-referenced-by-count":73,"title":["Factoring multivariate polynomials via partial differential equations"],"prefix":"10.1090","volume":"72","author":[{"given":"Shuhong","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2002,2,28]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/0222024","article-title":"Factoring rational polynomials over the complex numbers","volume":"22","author":"Bajaj, Chanderjit","year":"1993","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"2","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","article-title":"Factoring polynomials over finite fields","volume":"46","author":"Berlekamp, E. R.","year":"1967","journal-title":"Bell System Tech. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0005-8580","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"713","DOI":"10.2307\/2004849","article-title":"Factoring polynomials over large finite fields","volume":"24","author":"Berlekamp, E. R.","year":"1970","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"Blum, Lenore","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0387982817"},{"key":"5","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":"6","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"},{"issue":"154","key":"7","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/2007663","article-title":"A new algorithm for factoring polynomials over finite fields","volume":"36","author":"Cantor, David G.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","first-page":"139","article-title":"G\u00e9n\u00e9ralisation de l\u2019\u00e9quation de Hesse","volume":"59","author":"Germay, R. H. J.","year":"1939","journal-title":"Ann. Soc. Sci. Bruxelles S\\'{e}r. I","ISSN":"https:\/\/id.crossref.org\/issn\/0037-959X","issn-type":"print"},{"issue":"5","key":"9","first-page":"1073","article-title":"Efficient factorization of polynomials over local fields","volume":"293","author":"Chistov, A. L.","year":"1987","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"key":"10","isbn-type":"print","first-page":"1509","article-title":"Efficient factoring polynomials over local fields and its applications","author":"Chistov, Alexandre L.","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/4431700471"},{"key":"11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0024-3795(93)90235-G","article-title":"Solving linear equations over \ud835\udc3a\ud835\udc39(2): block Lanczos algorithm","volume":"192","author":"Coppersmith, Don","year":"1993","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"205","key":"12","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/2153413","article-title":"Solving homogeneous linear equations over \ud835\udc3a\ud835\udc39(2) via block Wiedemann algorithm","volume":"62","author":"Coppersmith, Don","year":"1994","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"13","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6911-1","volume-title":"Using algebraic geometry","volume":"185","author":"Cox, David","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0387984879"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0220001","article-title":"Absolute factorization of polynomials: a geometric approach","volume":"20","author":"Duval, Dominique","year":"1991","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","unstructured":"S. Gao (Gao\u2019s papers are available at http:\/\/www.math.clemson.edu\/faculty\/Gao), \u201cAbsolute irreducibility of polynomials via Newton polytopes\u201d, J. of Algebra 237 (2001), 501\u2013520.","DOI":"10.1006\/jabr.2000.8586"},{"key":"16","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.","DOI":"10.1007\/s00454-001-0024-0"},{"key":"17","unstructured":"S. Gao and A. G. B. Lauder, \u201cFactoring polynomials via polytopes\u201d, in preparation."},{"key":"18","unstructured":"S. Gao and A. G. B. Lauder, \u201cFast absolute irreducibility testing via Newton polytopes,\u201d preprint, 2000. (13 pages)"},{"key":"19","unstructured":"S. Gao and A. G. B. Lauder, \u201cHensel lifting and bivariate polynomial factorisation over finite fields,\u201d to appear in Mathematics of Computation. (17 pages)"},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1090\/conm\/168\/01691","article-title":"Berlekamp\u2019s and Niederreiter\u2019s polynomial factorization algorithms","author":"Gao, Shuhong","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821851837"},{"issue":"2","key":"21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","article-title":"Irreducibility of multivariate polynomials","volume":"31","author":"von zur Gathen, Joachim","year":"1985","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"key":"22","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"issue":"171","key":"23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.2307\/2008063","article-title":"Factorization of multivariate polynomials over finite fields","volume":"45","author":"von zur Gathen, J.","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","article-title":"Irreducibility of multivariate polynomials","volume":"31","author":"von zur Gathen, Joachim","year":"1985","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"3","key":"25","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":"26","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"},{"key":"27","first-page":"139","article-title":"G\u00e9n\u00e9ralisation de l\u2019\u00e9quation de Hesse","volume":"59","author":"Germay, R. H. J.","year":"1939","journal-title":"Ann. Soc. Sci. Bruxelles S\\'{e}r. I","ISSN":"https:\/\/id.crossref.org\/issn\/0037-959X","issn-type":"print"},{"issue":"6","key":"28","first-page":"1302","article-title":"Fast factorization of polynomials into irreducible ones and the solution of systems of algebraic equations","volume":"275","author":"Grigor\u2032ev, D. Yu.","year":"1984","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"key":"29","series-title":"Graduate Texts in Mathematics, No. 52","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3849-0","volume-title":"Algebraic geometry","author":"Hartshorne, Robin","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0387902449"},{"issue":"2","key":"30","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/0214035","article-title":"Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization","volume":"14","author":"Kaltofen, Erich","year":"1985","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"2","key":"31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01810297","article-title":"Computing the irreducible real factors and components of an algebraic curve","volume":"1","author":"Kaltofen, Erich","year":"1990","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"2","key":"32","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1006\/jcss.1995.1023","article-title":"Effective Noether irreducibility forms and applications","volume":"50","author":"Kaltofen, Erich","year":"1995","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"key":"33","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55984-1","volume-title":"Compiler construction","volume":"641","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3540559841"},{"issue":"223","key":"34","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"},{"issue":"3","key":"35","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","article-title":"Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators","volume":"9","author":"Kaltofen, Erich","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"36","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-38424-3","volume-title":"Advances in cryptology---CRYPTO '90","volume":"537","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/3540545085"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0747-7171(08)80026-0","article-title":"Integration of rational functions: rational computation of the logarithmic part","volume":"9","author":"Lazard, D.","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1-2","key":"38","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0304-3975(84)90117-8","article-title":"Factoring multivariate integral polynomials","volume":"34","author":"Lenstra, A. K.","year":"1984","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"2","key":"39","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0022-0000(85)90016-9","article-title":"Factoring multivariate polynomials over finite fields","volume":"30","author":"Lenstra, A. K.","year":"1985","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"3","key":"40","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1137\/0216040","article-title":"Factoring multivariate polynomials over algebraic number fields","volume":"16","author":"Lenstra, Arjen K.","year":"1987","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"4","key":"41","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"42","isbn-type":"print","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/3-540-49264-X_9","article-title":"A block Lanczos algorithm for finding dependencies over \ud835\udc3a\ud835\udc39(2)","author":"Montgomery, Peter L.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540594094"},{"key":"43","series-title":"Grundlehren der Mathematischen Wissenschaften, No. 221","volume-title":"Algebraic geometry. I","author":"Mumford, David","year":"1976"},{"key":"44","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":"45","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"},{"issue":"2","key":"46","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/S0036144595288554","article-title":"Solving a polynomial equation: some history and recent progress","volume":"39","author":"Pan, Victor Y.","year":"1997","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"key":"47","isbn-type":"print","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-58691-1_47","article-title":"A new modular interpolation algorithm for factoring multivariate polynomials (extended abstract)","author":"Rubinfeld, Ronitt","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"48","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":"49","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"},{"key":"50","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":"4","key":"51","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz, J. T.","year":"1980","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"52","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1002\/sapm1939181153","article-title":"A function related to the series for \ud835\udc52^{\ud835\udc52^{\ud835\udc65}}","volume":"18","author":"Epstein, Leo F.","year":"1939","journal-title":"J. Math. Phys. Mass. Inst. Tech.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-1421","issn-type":"print"},{"issue":"1","key":"53","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"32","author":"Wiedemann, Douglas H.","year":"1986","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"54","isbn-type":"print","first-page":"216","article-title":"Probabilistic algorithms for sparse polynomials","author":"Zippel, Richard","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/3540095195"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2003-72-242\/S0025-5718-02-01428-X\/S0025-5718-02-01428-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-242\/S0025-5718-02-01428-X\/S0025-5718-02-01428-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:14:51Z","timestamp":1776726891000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-242\/S0025-5718-02-01428-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,2,28]]},"references-count":54,"journal-issue":{"issue":"242","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0025-5718-02-01428-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-02-01428-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":[[2002,2,28]]}}}