{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:03Z","timestamp":1781077863452,"version":"3.54.1"},"reference-count":33,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1990,3,1]],"date-time":"1990-03-01T00:00:00Z","timestamp":636249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8539,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Symbolic Computation"],"published-print":{"date-parts":[[1990,3]]},"DOI":"10.1016\/s0747-7171(08)80015-6","type":"journal-article","created":{"date-parts":[[2008,5,9]],"date-time":"2008-05-09T09:45:58Z","timestamp":1210326358000},"page":"301-320","source":"Crossref","is-referenced-by-count":125,"title":["Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators"],"prefix":"10.1016","volume":"9","author":[{"given":"Erich","family":"Kaltofen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barry M.","family":"Trager","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0747-7171(08)80015-6_bib1","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","article-title":"The complexity of partial derivatives","volume":"22","author":"Baur","year":"1983","journal-title":"Theoretical Comp. Sci."},{"key":"10.1016\/S0747-7171(08)80015-6_bib2","series-title":"Proc. 20th Annual ACM Symp. Theory Comp.","first-page":"301","article-title":"A deterministic algorithm for sparse multivariate polynomial interpolation","author":"Ben-Or","year":"1988"},{"key":"10.1016\/S0747-7171(08)80015-6_bib3","article-title":"The Complexity of Robot Motion Planning","author":"Canny","year":"1988"},{"key":"10.1016\/S0747-7171(08)80015-6_bib4","series-title":"Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput.","first-page":"121","article-title":"Solving systems of non-linear polynomial equations faster","author":"Canny","year":"1989"},{"key":"10.1016\/S0747-7171(08)80015-6_bib5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","article-title":"A taxonomy of problems with fast parallel algorithms","volume":"64","author":"Cook","year":"1985","journal-title":"Inf. Control"},{"key":"10.1016\/S0747-7171(08)80015-6_bib6","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01389312","article-title":"Eine Methode zur Berechnung s\u00e4mtlicher L\u00f6sungen von Polynomgleichungs-systemen","volume":"29","author":"Drexler","year":"1977","journal-title":"Numer. Math."},{"issue":"3","key":"10.1016\/S0747-7171(08)80015-6_bib7","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/44128.214376","article-title":"DAGWOOD: A system for manipulating polynomials given by straight-line programs","volume":"14","author":"Freeman","year":"1988","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0747-7171(08)80015-6_bib8","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF01582106","article-title":"Finding all solutions to polynomial systems and other systems of equations","volume":"16","author":"Garcia","year":"1979","journal-title":"Math. Program."},{"key":"10.1016\/S0747-7171(08)80015-6_bib9","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1137\/0213050","article-title":"Parallel algorithms for algebraic problems","volume":"13","author":"von zur Gathen","year":"1984","journal-title":"SIAM J. Comp."},{"key":"10.1016\/S0747-7171(08)80015-6_bib10","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","article-title":"Irreducibility of multivariate polynomials","volume":"31","author":"von zur Gathen","year":"1985","journal-title":"J. Comp. System Sci."},{"key":"10.1016\/S0747-7171(08)80015-6_bib11","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1137\/0215030","article-title":"Representations and parallel computations for rational functions","volume":"15","author":"von zur Gathen","year":"1986","journal-title":"SIAM J. Comp."},{"key":"10.1016\/S0747-7171(08)80015-6_bib12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(85)90044-3","article-title":"Factoring sparse multivariate polynomials","volume":"31","author":"von zur Gathen","year":"1985","journal-title":"J. Comp. System Sci."},{"key":"10.1016\/S0747-7171(08)80015-6_bib13","author":"Golub","year":"1987"},{"issue":"1","key":"10.1016\/S0747-7171(08)80015-6_bib14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/1014001","article-title":"The Pad\u00e9 table and its relation to certain algorithms of numerical analysis","volume":"14","author":"Gragg","year":"1972","journal-title":"SIAM Review"},{"key":"10.1016\/S0747-7171(08)80015-6_bib15","doi-asserted-by":"crossref","DOI":"10.1137\/0219073","article-title":"Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields","author":"Grigoryev","year":"1988"},{"key":"10.1016\/S0747-7171(08)80015-6_bib16","series-title":"Computer Algebra","first-page":"95","article-title":"Polynomial factorization","author":"Kaltofen","year":"1982"},{"key":"10.1016\/S0747-7171(08)80015-6_bib17","doi-asserted-by":"crossref","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","year":"1985","journal-title":"SIAM J. Comp."},{"key":"10.1016\/S0747-7171(08)80015-6_bib18","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(85)80056-5","article-title":"Effective Hilbert irreducibility","volume":"66","author":"Kaltofen","year":"1985","journal-title":"Information and Control"},{"key":"10.1016\/S0747-7171(08)80015-6_bib19","series-title":"Proc. 18th ACM Symp. Theory Comp.","first-page":"330","article-title":"Uniform closure properties of p-computable functions","author":"Kaltofen","year":"1986"},{"issue":"1","key":"10.1016\/S0747-7171(08)80015-6_bib20","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/42267.45069","article-title":"Greatest common divisors of polynomials given by straight-line programs","volume":"35","author":"Kaltofen","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/S0747-7171(08)80015-6_bib21","series-title":"Randomness in Computation","first-page":"375","article-title":"Factorization of polynomials given by straight-line programs","volume":"5","author":"Kaltofen","year":"1989"},{"key":"10.1016\/S0747-7171(08)80015-6_bib22","series-title":"Proc. ISSAC '88","first-page":"467","article-title":"Improved sparse multivariate polynomial interpolation algorithms","volume":"358","author":"Kaltofen","year":"1988"},{"key":"10.1016\/S0747-7171(08)80015-6_bib23","author":"Knuth","year":"1981"},{"key":"10.1016\/S0747-7171(08)80015-6_bib24","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/0214015","article-title":"Factoring polynomials over algebraic number fields","volume":"14","author":"Landau","year":"1985","journal-title":"SIAM J. Comp."},{"issue":"2","key":"10.1016\/S0747-7171(08)80015-6_bib25","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1090\/S0273-0979-1988-15639-X","article-title":"Numerically determining solutions of systems of polynomial equations","volume":"18","author":"Li","year":"1988","journal-title":"AMS Bulletin"},{"key":"10.1016\/S0747-7171(08)80015-6_bib26","article-title":"Algebraic theory of modular systems","volume":"19","author":"Macaulay","year":"1916","journal-title":"Cambridge Tracts"},{"key":"10.1016\/S0747-7171(08)80015-6_bib27","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/321879.321890","article-title":"Multivariate polynomial factorization","volume":"22","author":"Musser","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/S0747-7171(08)80015-6_bib28","series-title":"Proc. 1976 ACM Symp. Symbolic Algebraic Comp.","first-page":"219","article-title":"Algebraic factoring and rational function integration","author":"Trager","year":"1976"},{"key":"10.1016\/S0747-7171(08)80015-6_bib29","first-page":"253","article-title":"Reducibility by algebraic projections","volume":"28","author":"Valiant","year":"1982","journal-title":"L'Enseignement math\u00e9matique"},{"key":"10.1016\/S0747-7171(08)80015-6_bib30","author":"van der Waerden","year":"1953"},{"key":"10.1016\/S0747-7171(08)80015-6_bib31","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"IT-32","author":"Wiedemann","year":"1986","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/S0747-7171(08)80015-6_bib32","doi-asserted-by":"crossref","DOI":"10.1016\/S0747-7171(08)80018-1","article-title":"Interpolating polynomials from their values","author":"Zippel","year":"1990","journal-title":"J. Symbolic Comput."},{"issue":"181","key":"10.1016\/S0747-7171(08)80015-6_bib33","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0025-5718-1988-0917824-7","article-title":"A simple homotopy method for determining all isolated solutions to polynomial systems","volume":"50","author":"Zulehner","year":"1988","journal-title":"Math. Comp."}],"container-title":["Journal of Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717108800156?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717108800156?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,12,28]],"date-time":"2018-12-28T22:58:59Z","timestamp":1546037939000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0747717108800156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["S0747717108800156"],"URL":"https:\/\/doi.org\/10.1016\/s0747-7171(08)80015-6","relation":{},"ISSN":["0747-7171"],"issn-type":[{"value":"0747-7171","type":"print"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}