{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T15:36:42Z","timestamp":1790869002630,"version":"4.1.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>Consider a polynomial f with an arbitrary but fixed number of variables and with integral coefficients. We present an algorithm which reduces the problem of finding the irreducible factors of f in polynomial-time in the total degree of f and the coefficient lengths of f to factoring a univariate integral polynomial. Together with A. Lenstra\u2019s,.H. Lenstra\u2019s and L. Lov\u00e1sz\u2019 polynomial-time factorization algorithm for univariate integral polynomials [Math. Ann., 261 (1982), pp. 515\u2013534] this algorithm implies the following theorem. Factoring an integral polynomial with a fixed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree and the size of its coefficients. Our algorithm can be generalized to factoring multivariate polynomials with coefficients in algebraic number fields and finite fields in polynomial-time. We also present a different algorithm, based on an effective version of a Hilbert Irreducibility Theorem, which polynomial-time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polynomials for irreduciblity.<\/jats:p>","DOI":"10.1137\/0214035","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"469-489","source":"Crossref","is-referenced-by-count":94,"title":["Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization"],"prefix":"10.1137","volume":"14","author":[{"given":"Erich","family":"Kaltofen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321665"},{"key":"R3","unstructured":"A. L. Chistov, D. Y. Grigoryev,  Polynomial-time factoring of the multivariable polynomials over a global field,  1982, Lomi preprint E-5-82, Leningrad"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206597"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01174354"},{"key":"R6","volume-title":"The theory of matrices. Vols. 1","author":"Gantmacher F. R.","year":"1959"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. von Zur Gathen,  Factoring sparse multivariate polynomials,  Proc. 1983 IEEE Symposium on Foundations of Computer Science,  172\u2013197","DOI":"10.1109\/SFCS.1983.15"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036913"},{"key":"R9","volume-title":"Transcendental and algebraic numbers","author":"Gel'fand A. O.","year":"1960"},{"key":"R10","volume-title":"An introduction to the theory of numbers","author":"Hardy G. H.","year":"1979"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1892.110.104"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Kaltofen,  A polynomial reduction from multivariate to bivariate integral polynomial factorization,  Proc. 1982 ACM Symposium Theory of Computers,  261\u2013266","DOI":"10.1145\/800070.802200"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.56"},{"key":"R14","unstructured":"E. Kaltofen, Ph.D. Thesis,  On the complexity of factoring polynomials with integer coefficients, Rensselaer Polytechnic Institute, Troy, NY,  1982, December"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12868-9_107"},{"key":"R16","volume-title":"The art of computer programming. Vol. 2. Seminumerical Algorithms","author":"Knuth Donald E.","year":"1981"},{"key":"R17","first-page":"1","volume":"92","author":"Kronecker L.","year":"1882","journal-title":"J. Reine Angew. Math."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322068"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0214015"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12868-9_108"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra,  Factoring multivariate polynomials over a finite field,  Proc. 1983 ACM Symposium on Theory of Computers,  189\u2013192","DOI":"10.1145\/800061.808748"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/321784.321787"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0354624-3"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Moses, D. Y. Y. Yun,  The EZGCD algorithm,  Proc. 1973 ACM National Conference,  159\u2013166","DOI":"10.1145\/800192.805698"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321890"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"B. M. Trager,  R.  Jenks,  Algebraic factoring and rational function integration,  Proc. ACM Symposium on Symbolic and Algebraic Computations,  1976,  219\u2013226","DOI":"10.1145\/800205.806338"},{"key":"R28","volume-title":"Modern Algebra, Vol. l","author":"van der Waerden B. L.","year":"1953"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1978-0568284-3"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0208022"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355709"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"D. Y. Y. Yun,  R.  Jenks,  On squarefree decomposition algorithms,  Proc. ACM Symposium on Symbolic and Algebraic Computations 1976 ACM,  1977,  26\u201335","DOI":"10.1145\/800205.806320"},{"key":"R33","unstructured":"D. Y. Y. Yun,  On the equivalence of polynomial GCD and squarefree factorization problems,  Proc. MACSYMA User's Conference 77 NASA, Washington, DC,  1977,  65\u201370"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/1089257.1089258"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"R. E. Zippel, Ph.D. Thesis,  Probabilistic algorithms for sparse polynomials, Massachusetts Institute of Technology, Cambridge,  1979 0418.68040","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:00Z","timestamp":1787337780000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214035"],"URL":"https:\/\/doi.org\/10.1137\/0214035","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}