{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T13:10:08Z","timestamp":1751807408171,"version":"3.41.0"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319999562"},{"type":"electronic","value":"9783319999579"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-99957-9_2","type":"book-chapter","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T08:26:31Z","timestamp":1534839991000},"page":"19-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Methodologies of Symbolic Computation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3982-7545","authenticated-orcid":false,"given":"James","family":"Davenport","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"unstructured":"Abbott, J.A.: Factorisation of polynomials over algebraic number fields. Ph.D. thesis, University of Bath (1988)","key":"2_CR1"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.jsc.2012.09.004","volume":"50","author":"JA Abbott","year":"2013","unstructured":"Abbott, J.A.: Bounds on factors in $${{\\bf Z}}[x]$$Z[x]. J. Symb. Comp. 50, 532\u2013563 (2013)","journal-title":"J. Symb. Comp."},{"unstructured":"Amzallag, E., Pogudin, G., Sun, M., Vo, N.T.: Complexity of triangular representations of algebraic sets. https:\/\/arxiv.org\/abs\/1609.09824v6 (2018)","key":"2_CR3"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0747-7171(02)00140-2","volume":"35","author":"EA Arnold","year":"2003","unstructured":"Arnold, E.A.: Modular algorithms for computing Gr\u00f6bner bases. J. Symb. Comp. 35, 403\u2013419 (2003)","journal-title":"J. Symb. Comp."},{"key":"2_CR5","first-page":"565","volume":"22","author":"EH Bareiss","year":"1968","unstructured":"Bareiss, E.H.: Sylvester\u2019s identity and multistep integer-preserving Gaussian elimination. Math. Comp. 22, 565\u2013578 (1968)","journal-title":"Math. Comp."},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","volume":"46","author":"ER Berlekamp","year":"1967","unstructured":"Berlekamp, E.R.: Factoring polynomials over finite fields. Bell. Syst. Tech. J. 46, 1853\u20131859 (1967)","journal-title":"Bell. Syst. Tech. J."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"ER Berlekamp","year":"1970","unstructured":"Berlekamp, E.R.: Factoring polynomials over large finite fields. Math. Comp. 24, 713\u2013735 (1970)","journal-title":"Math. Comp."},{"unstructured":"Brain, M.N., Davenport, J.H., Griggio, A.: Benchmarking solvers, SAT-style. In: SC$$^2$$2 2017 Satisfiability Checking and Symbolic Computation CEUR Workshop 1974, no. RP3, pp. 1\u201315 (2017)","key":"2_CR8"},{"doi-asserted-by":"crossref","unstructured":"Brown, W.S.: On Euclid\u2019s algorithm and the computation of polynomial greatest common divisors. In: Proceedings of SYMSAC 1971, pp. 195\u2013211 (1971)","key":"2_CR9","DOI":"10.1145\/800204.806288"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321662.321664","volume":"18","author":"WS Brown","year":"1971","unstructured":"Brown, W.S.: On Euclid\u2019s algorithm and the computation of polynomial greatest common divisors. J. ACM 18, 478\u2013504 (1971)","journal-title":"J. ACM"},{"unstructured":"Buchberger, B.: Ein Algorithmus zum Auffinden des Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.D. thesis, Math. Inst. University of Innsbruck (1965)","key":"2_CR11"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.jsc.2015.11.008","volume":"75","author":"C Chen","year":"2016","unstructured":"Chen, C., Moreno Maza, M.: Quantifier elimination by cylindrical algebraic decomposition based on regular chains. J. Symb. Comp. 75, 74\u201393 (2016)","journal-title":"J. Symb. Comp."},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1090\/S1061-0022-09-01081-4","volume":"20","author":"AL Chistov","year":"2009","unstructured":"Chistov, A.L.: Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal. St. Petersb. Math. J. 20, 983\u20131001 (2009)","journal-title":"St. Petersb. Math. J."},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1145\/321371.321381","volume":"14","author":"GE Collins","year":"1967","unstructured":"Collins, G.E.: Subresultants and reduced polynomial remainder sequences. J. ACM 14, 128\u2013142 (1967)","journal-title":"J. ACM"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume-title":"Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern","author":"GE Collins","year":"1975","unstructured":"Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Brakhage, H. (ed.) Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern. LNCS, vol. 33, pp. 134\u2013183. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_17"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.4064\/aa-58-1-79-87","volume":"58","author":"D Coppersmith","year":"1991","unstructured":"Coppersmith, D., Davenport, J.H.: Polynomials whose powers are sparse. Acta Arith. 58, 79\u201387 (1991)","journal-title":"Acta Arith."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.4169\/amer.math.monthly.118.01.003","volume":"118","author":"DA Cox","year":"2011","unstructured":"Cox, D.A.: Why Eisenstein proved the Eisenstein criterion and why Sch\u00f6nemann discovered it first. Am. Math. Monthly 118, 3\u201331 (2011)","journal-title":"Am. Math. Monthly"},{"key":"2_CR18","series-title":"Undergraduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties, and Algorithms","author":"DA Cox","year":"2015","unstructured":"Cox, D.A., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-0-387-35651-8"},{"doi-asserted-by":"crossref","unstructured":"Davenport, J.H., Carette, J.: The sparsity challenges. In: Watt, S., et al. (eds.) Proceeding of SYNASC 2009, pp. 3\u20137 (2010)","key":"2_CR19","DOI":"10.1109\/SYNASC.2009.62"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1098\/rspl.1866.0037","volume":"15","author":"CL Dodgson","year":"1866","unstructured":"Dodgson, C.L.: Condensation of determinants, being a new and brief method for computing their algebraic value. Proc. R. Soc. Ser. A 15, 150\u2013155 (1866)","journal-title":"Proc. R. Soc. Ser. A"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-45641-6_12","volume-title":"Computer Algebra in Scientific Computing","author":"M England","year":"2016","unstructured":"England, M., Davenport, J.H.: The complexity of cylindrical algebraic decomposition with respect to polynomial degree. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2016. LNCS, vol. 9890, pp. 172\u2013192. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-45641-6_12"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/jsco.1993.1011","volume":"15","author":"M Kalkbrener","year":"1993","unstructured":"Kalkbrener, M.: A generalized Euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comp. 15, 143\u2013167 (1993)","journal-title":"J. Symb. Comp."},{"doi-asserted-by":"crossref","unstructured":"Kaltofen, E., Li, B., Yang, Z., Zhi, L.: Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In: Jeffrey, D.J. (ed.) Proceedings of ISSAC 2008, pp. 155\u2013164 (2008)","key":"2_CR23","DOI":"10.1145\/1390768.1390792"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jun, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"22","key":"2_CR25","first-page":"124","volume":"14","author":"J Liouville","year":"1833","unstructured":"Liouville, J.: Premier M\u00e9moire sur la D\u00e9termination des Int\u00e9grales dont la Valeur est Alg\u00e9brique. J. l\u2019\u00c9cole Polytech. 14(22), 124\u2013148 (1833)","journal-title":"J. l\u2019\u00c9cole Polytech."},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.jsc.2011.12.018","volume":"49","author":"EW Mayr","year":"2013","unstructured":"Mayr, E.W., Ritscher, S.: Dimension-dependent bounds for Gr\u00f6bner bases of polynomial ideals. J. Symb. Comp. 49, 78\u201394 (2013)","journal-title":"J. Symb. Comp."},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1090\/S0025-5718-1974-0354624-3","volume":"28","author":"M Mignotte","year":"1974","unstructured":"Mignotte, M.: An inequality about factors of polynomials. Math. Comp. 28, 1153\u20131157 (1974)","journal-title":"Math. Comp."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1145\/322063.322071","volume":"25","author":"DR Musser","year":"1978","unstructured":"Musser, D.R.: On the efficiency of a polynomial irreducibility test. J. ACM 25, 271\u2013282 (1978)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Nguy n, P.Q., Stehl\u00e9, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39, 874\u2013903 (2009)","key":"2_CR29","DOI":"10.1137\/070705702"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/rsa.20632","volume":"49","author":"R Pemantle","year":"2015","unstructured":"Pemantle, R., Peres, Y., Rivin, I.: Four random permutations conjugated by an adversary generate $$S_n$$Sn with high probability. Random Struct. Algorithms 49, 409\u2013428 (2015)","journal-title":"Random Struct. Algorithms"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1137\/0207036","volume":"7","author":"DA Plaisted","year":"1978","unstructured":"Plaisted, D.A.: Some polynomial and integer divisibility problems are $$NP$$NP-hard. SIAM J. Comp. 7, 458\u2013464 (1978)","journal-title":"SIAM J. Comp."},{"doi-asserted-by":"crossref","unstructured":"Roche, D.S.: What can (and can\u2019t) we do with sparse polynomials? In: Proceedings of ISSAC 2018, pp. 25\u201330 (2018)","key":"2_CR32","DOI":"10.1145\/3208976.3209027"},{"key":"2_CR33","first-page":"394","volume":"12","author":"T Sasaki","year":"1989","unstructured":"Sasaki, T., Sasaki, M.: Analysis of accuracy decreasing in polynomial remainder sequence and floating-point number coefficients. J. Inform. Proc. 12, 394\u2013403 (1989)","journal-title":"J. Inform. Proc."},{"doi-asserted-by":"crossref","unstructured":"Sasaki, T., Yamaguchi, S.: An analysis of cancellation error in multivariate Hensel construction with floating-point arithmetic. In: Gloor, O. (ed.) Proceedings of ISSAC 1998, pp. 1\u20138 (1998)","key":"2_CR34","DOI":"10.1145\/281508.281521"},{"doi-asserted-by":"crossref","unstructured":"Schinzel, A.: On the greatest common divisor of two univariate polynomials, I. In: A Panorama of Number Theory or the View from Baker\u2019s Garden, pp. 337\u2013352. C.U.P. (2003)","key":"2_CR35","DOI":"10.1017\/CBO9780511542961.022"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/S0378-4754(96)00027-4","volume":"42","author":"K Shirayanagi","year":"1996","unstructured":"Shirayanagi, K.: Floating point Gr\u00f6bner bases. Math. Comput. Simul. 42, 509\u2013528 (1996)","journal-title":"Math. Comput. Simul."},{"unstructured":"Swinnerton-Dyer, H.P.F.: Letter to E.H. Berlekamp. Mentioned in [7] (1970)","key":"2_CR37"},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-7091-9459-1_3","volume-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition","author":"A Tarski","year":"1998","unstructured":"Tarski, A.: A decision method for elementary algebra and geometry. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 24\u201384. Springer, Vienna (1998). https:\/\/doi.org\/10.1007\/978-3-7091-9459-1_3"},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1090\/S0025-5718-1978-0568284-3","volume":"32","author":"PS Wang","year":"1978","unstructured":"Wang, P.S.: An improved multivariable polynomial factorising algorithm. Math. Comp. 32, 1215\u20131231 (1978)","journal-title":"Math. Comp."},{"issue":"2","key":"2_CR40","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1089292.1089293","volume":"16","author":"PS Wang","year":"1982","unstructured":"Wang, P.S., Guy, M.J.T., Davenport, J.H.: $$p$$p-adic reconstruction of rational numbers. SIGSAM Bull. 16(2), 2\u20133 (1982)","journal-title":"SIGSAM Bull."},{"key":"2_CR41","first-page":"207","volume":"4","author":"W-T Wu","year":"1984","unstructured":"Wu, W.-T.: Basic principles of mechanical theorem proving in elementary geometries. J. Syst. Sci. and Math. Sci. (Beijing) 4, 207\u2013235 (1984)","journal-title":"J. Syst. Sci. and Math. Sci. (Beijing)"},{"key":"2_CR42","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0022-314X(69)90047-X","volume":"1","author":"H Zassenhaus","year":"1969","unstructured":"Zassenhaus, H.: On Hensel factorization I. J. Number Theor. 1, 291\u2013311 (1969)","journal-title":"J. Number Theor."},{"key":"2_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3188-3","volume-title":"Effective Polynomial Computation","author":"RE Zippel","year":"1993","unstructured":"Zippel, R.E.: Effective Polynomial Computation. Kluwer Academic Publishers, Boston (1993)"}],"container-title":["Lecture Notes in Computer Science","Artificial Intelligence and Symbolic Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-99957-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T12:50:56Z","timestamp":1751806256000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-99957-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319999562","9783319999579"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-99957-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}