{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T03:57:03Z","timestamp":1775102223833,"version":"3.50.1"},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T00:00:00Z","timestamp":1584576000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T00:00:00Z","timestamp":1584576000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s10208-020-09453-0","type":"journal-article","created":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T20:02:40Z","timestamp":1584648160000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["On the Complexity Exponent of Polynomial System Solving"],"prefix":"10.1007","volume":"21","author":[{"given":"Joris","family":"van der Hoeven","sequence":"first","affiliation":[]},{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,19]]},"reference":[{"key":"9453_CR1","doi-asserted-by":"crossref","unstructured":"M.\u00a0Agrawal, N.\u00a0Kayal, and N.\u00a0Saxena. PRIMES is in P. Ann. Math., pages 781\u2013793, 2004.","DOI":"10.4007\/annals.2004.160.781"},{"issue":"1","key":"9453_CR2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10208-014-9214-z","volume":"15","author":"B Bank","year":"2015","unstructured":"B.\u00a0Bank, M.\u00a0Giusti, J.\u00a0Heintz, G.\u00a0Lecerf, G.\u00a0Matera, and P.\u00a0Solern\u00f3. Degeneracy loci and polynomial equation solving. Found. Comput. Math., 15(1):159\u2013184, 2015.","journal-title":"Found. Comput. Math."},{"key":"9453_CR3","unstructured":"M.\u00a0Bardet. \u00c9tude des syst\u00e8mes alg\u00e9briques surd\u00e9termin\u00e9s. Applications aux codes correcteurs et \u00e0 la cryptographie. PhD thesis, Universit\u00e9 Pierre et Marie Curie - Paris VI, 2004. https:\/\/tel.archives-ouvertes.fr\/tel-00449609."},{"key":"9453_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jsc.2014.09.025","volume":"70","author":"M Bardet","year":"2015","unstructured":"M.\u00a0Bardet, J.-C.\u00a0Faug\u00e8re, and B.\u00a0Salvy. On the complexity of the $$F_5$$ Gr\u00f6bner basis algorithm. J.\u00a0Symbolic Comput., 70:49\u201370, 2015.","journal-title":"J. Symbolic Comput."},{"key":"9453_CR5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"SJ Berkowitz","year":"1984","unstructured":"S.\u00a0J.\u00a0Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inform. Process. Lett., 18:147\u2013150, 1984.","journal-title":"Inform. Process. Lett."},{"key":"9453_CR6","doi-asserted-by":"crossref","unstructured":"J.\u00a0Berthomieu, J.\u00a0van\u00a0der Hoeven, and G.\u00a0Lecerf. Relaxed algorithms for p-adic numbers. J.\u00a0Th\u00e9or. Nombres Bordeaux, 23(3), 2011.","DOI":"10.5802\/jtnb.777"},{"issue":"6","key":"9453_CR7","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00200-013-0200-5","volume":"24","author":"J Berthomieu","year":"2013","unstructured":"J.\u00a0Berthomieu, G.\u00a0Lecerf, and G.\u00a0Quintin. Polynomial root finding over local rings and application to error correcting codes. Appl. Alg. Eng. Comm. Comp., 24(6):413\u2013443, 2013.","journal-title":"Appl. Alg. Eng. Comm. Comp."},{"key":"9453_CR8","unstructured":"A.\u00a0Bostan, F.\u00a0Chyzak, M.\u00a0Giusti, R.\u00a0Lebreton, G.\u00a0Lecerf, B.\u00a0Salvy, and \u00c9 Schost. Algorithmes Efficaces en Calcul Formel. Fr\u00e9d\u00e9ric Chyzak (self-published), Palaiseau, 2017. Electronic version available from https:\/\/hal.archives-ouvertes.fr\/AECF."},{"issue":"1","key":"9453_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jsc.2005.07.001","volume":"41","author":"A Bostan","year":"2006","unstructured":"A.\u00a0Bostan, Ph.\u00a0Flajolet, B.\u00a0Salvy, and \u00c9.\u00a0Schost. Fast computation of special resultants. J.\u00a0Symbolic Comput., 41(1):1\u201329, 2006.","journal-title":"J. Symbolic Comput."},{"issue":"4","key":"9453_CR10","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","volume":"21","author":"A Bostan","year":"2005","unstructured":"A.\u00a0Bostan and \u00c9.\u00a0Schost. Polynomial evaluation and interpolation on special sets of points. J.\u00a0Complexity, 21(4):420\u2013446, 2005.","journal-title":"J. Complexity"},{"issue":"4","key":"9453_CR11","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/322092.322099","volume":"25","author":"RP Brent","year":"1978","unstructured":"R.\u00a0P.\u00a0Brent and H.\u00a0T.\u00a0Kung. Fast algorithms for manipulating formal power series. J.\u00a0ACM, 25(4):581\u2013595, 1978.","journal-title":"J. ACM"},{"issue":"3","key":"9453_CR12","doi-asserted-by":"crossref","first-page":"577","DOI":"10.2307\/1971361","volume":"126","author":"WD Brownawell","year":"1987","unstructured":"W.\u00a0D.\u00a0Brownawell. Bounds for the degrees in the Nullstellensatz. Annal. of Math., 126(3):577\u2013591, 1987.","journal-title":"Annal. of Math."},{"key":"9453_CR13","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser, M.\u00a0Clausen, and M.\u00a0A.\u00a0Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"9453_CR14","doi-asserted-by":"crossref","unstructured":"J.\u00a0F.\u00a0Canny, E.\u00a0Kaltofen, and L.\u00a0Yagati. Solving systems of nonlinear polynomial equations faster. In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201989, pages 121\u2013128. New York, NY, USA, 1989. ACM.","DOI":"10.1145\/74540.74556"},{"key":"9453_CR15","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"DG Cantor","year":"1991","unstructured":"D.\u00a0G.\u00a0Cantor and E.\u00a0Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Infor., 28:693\u2013701, 1991.","journal-title":"Acta Infor."},{"issue":"1","key":"9453_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s11856-012-0070-8","volume":"194","author":"J-M Couveignes","year":"2013","unstructured":"J.-M.\u00a0Couveignes and R.\u00a0Lercier. Fast construction of irreducible polynomials over finite fields. Israel J.\u00a0Math., 194(1):77\u2013105, 2013.","journal-title":"Israel J. Math."},{"issue":"2","key":"9453_CR17","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1090\/tran\/7437","volume":"371","author":"C D\u2019Andrea","year":"2019","unstructured":"C.\u00a0D\u2019Andrea, A.\u00a0Ostafe, I.\u00a0E.\u00a0Shparlinski, and M.\u00a0Sombra. Reduction modulo primes of systems of polynomial equations and algebraic dynamical systems. Trans. Amer. Math. Soc., 371(2):1169\u20131198, 2019.","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2","key":"9453_CR18","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.exmath.2007.07.001","volume":"26","author":"C Durvye","year":"2008","unstructured":"C.\u00a0Durvye and G.\u00a0Lecerf. A concise proof of the Kronecker polynomial system solver from scratch. Expo. Math., 26(2):101\u2013139, 2008.","journal-title":"Expo. Math."},{"key":"9453_CR19","doi-asserted-by":"crossref","unstructured":"J.-C.\u00a0Faug\u00e8re, P.\u00a0Gaudry, L.\u00a0Huot, and G.\u00a0Renault. Sub-cubic change of ordering for Gr\u00f6bner basis: a probabilistic approach. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, pages 170\u2013177. New York, NY, USA, 2014. ACM.","DOI":"10.1145\/2608628.2608669"},{"issue":"4","key":"9453_CR20","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1006\/jsco.1993.1051","volume":"16","author":"J-C Faug\u00e8re","year":"1993","unstructured":"J.-C.\u00a0Faug\u00e8re, P.\u00a0Gianni, D.\u00a0Lazard, and T.\u00a0Mora. Efficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering. J.\u00a0Symbolic Comput., 16(4):329\u2013344, 1993.","journal-title":"J. Symbolic Comput."},{"key":"9453_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern computer algebra","author":"J. zur von Gathen","year":"2013","unstructured":"J.\u00a0von\u00a0zur Gathen and J.\u00a0Gerhard. Modern computer algebra. Cambridge University Press, New York, 3rd edition, 2013.","edition":"3"},{"key":"9453_CR22","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.jco.2018.09.005","volume":"51","author":"N Gim\u00e9nez","year":"2019","unstructured":"N.\u00a0Gim\u00e9nez and G.\u00a0Matera. On the bit complexity of polynomial system solving. J.\u00a0Complexity, 51:20\u201367, 2019.","journal-title":"J. Complexity"},{"key":"9453_CR23","doi-asserted-by":"crossref","unstructured":"M.\u00a0Giusti. Some effectivity problems in polynomial ideal theory. In J.\u00a0Fitch, editor, EUROSAM 84: International Symposium on Symbolic and Algebraic Computation Cambridge, England, July 9\u201311, 1984, pages 159\u2013171. Berlin, Heidelberg, 1984. Springer Berlin Heidelberg.","DOI":"10.1007\/BFb0032839"},{"issue":"118","key":"9453_CR24","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0022-4049(97)00015-7","volume":"117","author":"M Giusti","year":"1997","unstructured":"M.\u00a0Giusti, K.\u00a0H\u00e4gele, J.\u00a0Heintz, J.\u00a0L.\u00a0Monta\u00f1a, J.\u00a0E.\u00a0Morais, and L.\u00a0M.\u00a0Pardo. Lower bounds for Diophantine approximations. J.\u00a0Pure Appl. Algebra, 117\/118:277\u2013317, 1997.","journal-title":"J. Pure Appl. Algebra"},{"issue":"1\u20133","key":"9453_CR25","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0022-4049(96)00099-0","volume":"124","author":"M Giusti","year":"1998","unstructured":"M.\u00a0Giusti, J.\u00a0Heintz, J.\u00a0E.\u00a0Morais, J.\u00a0Morgenstern, and L.\u00a0M.\u00a0Pardo. Straight-line programs in geometric elimination theory. J.\u00a0Pure Appl. Algebra, 124(1-3):101\u2013146, 1998.","journal-title":"J. Pure Appl. Algebra"},{"key":"9453_CR26","doi-asserted-by":"crossref","unstructured":"M.\u00a0Giusti, J.\u00a0Heintz, J.\u00a0E.\u00a0Morais, and L.\u00a0M.\u00a0Pardo. When polynomial equation systems can be \u201csolved\u201d fast? In Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), volume 948 of Lecture Notes in Comput. Sci., pages 205\u2013231. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60114-7_16"},{"issue":"1","key":"9453_CR27","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M Giusti","year":"2001","unstructured":"M.\u00a0Giusti, G.\u00a0Lecerf, and B.\u00a0Salvy. A Gr\u00f6bner free alternative for polynomial system solving. J.\u00a0complexity, 17(1):154\u2013211, 2001.","journal-title":"J. complexity"},{"issue":"3","key":"9453_CR28","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00200-015-0280-5","volume":"27","author":"B Grenet","year":"2016","unstructured":"B.\u00a0Grenet, J.\u00a0van der\u00a0Hoeven, and G.\u00a0Lecerf. Deterministic root finding over finite fields using Graeffe transforms. Appl. Alg. Eng. Comm. Comp., 27(3):237\u2013257, 2016.","journal-title":"Appl. Alg. Eng. Comm. Comp."},{"key":"9453_CR29","doi-asserted-by":"crossref","first-page":"101404","DOI":"10.1016\/j.jco.2019.03.004","volume":"54","author":"D Harvey","year":"2019","unstructured":"D.\u00a0Harvey and J.\u00a0van\u00a0der Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. J.\u00a0Complexity, 54:101404, 2019.","journal-title":"J. Complexity"},{"key":"9453_CR30","unstructured":"D.\u00a0Harvey and J.\u00a0van\u00a0der Hoeven. Integer multiplication in time $$O (n \\log n)$$. Technical Report, HAL, 2019. http:\/\/hal.archives-ouvertes.fr\/hal-02070778."},{"key":"9453_CR31","unstructured":"D.\u00a0Harvey and J.\u00a0van\u00a0der Hoeven. Polynomial multiplication over finite fields in time $$O (n \\log n)$$. Technical Report, HAL, 2019. http:\/\/hal.archives-ouvertes.fr\/hal-02070816."},{"issue":"3","key":"9453_CR32","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J Heintz","year":"1983","unstructured":"J.\u00a0Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci., 24(3):239\u2013277, 1983.","journal-title":"Theor. Comput. Sci."},{"key":"9453_CR33","unstructured":"J.\u00a0van\u00a0der Hoeven and G.\u00a0Lecerf. Modular composition via complex roots. Technical Report, CNRS & \u00c9cole polytechnique, 2017. http:\/\/hal.archives-ouvertes.fr\/hal-01455731."},{"key":"9453_CR34","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.jco.2018.05.002","volume":"48","author":"J van der Hoeven","year":"2018","unstructured":"J.\u00a0van\u00a0der Hoeven and G.\u00a0Lecerf. Modular composition via factorization. J.\u00a0Complexity, 48:36\u201368, 2018.","journal-title":"J. Complexity"},{"key":"9453_CR35","doi-asserted-by":"crossref","first-page":"101402","DOI":"10.1016\/j.jco.2019.03.002","volume":"55","author":"J van der Hoeven","year":"2019","unstructured":"J.\u00a0van\u00a0der Hoeven and G.\u00a0Lecerf. Accelerated tower arithmetic. J.\u00a0Complexity, 55:101402, 2019.","journal-title":"J. Complexity"},{"key":"9453_CR36","doi-asserted-by":"crossref","first-page":"101405","DOI":"10.1016\/j.jco.2019.04.001","volume":"56","author":"J van der Hoeven","year":"2020","unstructured":"J.\u00a0van\u00a0der Hoeven and G.\u00a0Lecerf. Fast multivariate multi-point evaluation revisited. J.\u00a0Complexity, 56:101405 2020.","journal-title":"J. Complexity"},{"key":"9453_CR37","unstructured":"J.\u00a0van\u00a0der Hoeven, G.\u00a0Lecerf, B.\u00a0Mourrain et\u00a0al. Mathemagix. From 2002. http:\/\/www.mathemagix.org."},{"issue":"2","key":"9453_CR38","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"Xiaohan Huang","year":"1998","unstructured":"Xiaohan Huang and V.\u00a0Y.\u00a0Pan. Fast rectangular matrix multiplication and applications. J.\u00a0Complexity, 14(2):257\u2013299, 1998.","journal-title":"J.\u00a0Complexity"},{"issue":"2\u20133","key":"9453_CR39","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0022-4049(01)00083-4","volume":"169","author":"G Jeronimo","year":"2002","unstructured":"G.\u00a0Jeronimo and J.\u00a0Sabia. Effective equidimensional decomposition of affine varieties. J.\u00a0Pure Appl. Algebra, 169(2\u20133):229\u2013248, 2002.","journal-title":"J. Pure Appl. Algebra"},{"key":"9453_CR40","doi-asserted-by":"crossref","unstructured":"E.\u00a0Kaltofen and V.\u00a0Shoup. Fast polynomial factorization over high algebraic extensions of finite fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201997, pages 184\u2013188. New York, NY, USA, 1997. ACM.","DOI":"10.1145\/258726.258777"},{"key":"9453_CR41","doi-asserted-by":"crossref","unstructured":"K.\u00a0S.\u00a0Kedlaya and C.\u00a0Umans. Fast modular composition in any characteristic. In FOCS\u201908: IEEE Conference on Foundations of Computer Science, pages 146\u2013155. Washington, DC, USA, 2008. IEEE Computer Society.","DOI":"10.1109\/FOCS.2008.13"},{"issue":"6","key":"9453_CR42","doi-asserted-by":"crossref","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"K.\u00a0S.\u00a0Kedlaya and C.\u00a0Umans. Fast polynomial factorization and modular composition. SIAM J.\u00a0Comput., 40(6):1767\u20131802, 2011.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9453_CR43","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1215\/S0012-7094-01-10934-4","volume":"109","author":"T Krick","year":"2001","unstructured":"T.\u00a0Krick, L.\u00a0M.\u00a0Pardo, and M.\u00a0Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Math. J., 109(3):521\u2013598, 2001.","journal-title":"Duke Math. J."},{"key":"9453_CR44","first-page":"1","volume":"92","author":"L Kronecker","year":"1882","unstructured":"L.\u00a0Kronecker. Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen. J.reine angew. Math., 92:1\u2013122, 1882.","journal-title":"J.reine angew. Math."},{"key":"9453_CR45","doi-asserted-by":"crossref","unstructured":"Y.\u00a0N.\u00a0Lakshman. On the complexity of computing a Gr\u00f6bner basis for the radical of a zero dimensional ideal. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC \u201990, pages 555\u2013563. New York, NY, USA, 1990. ACM.","DOI":"10.1145\/100216.100294"},{"key":"9453_CR46","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-1-4612-0441-1_15","volume-title":"Effective Methods in Algebraic Geometry","author":"YN Lakshman","year":"1991","unstructured":"Y.\u00a0N.\u00a0Lakshman. A single exponential bound on the complexity of computing Gr\u00f6bner bases of zero dimensional ideals. In T.\u00a0Mora and C.\u00a0Traverso, editors, Effective Methods in Algebraic Geometry, pages 227\u2013234. Boston, MA, 1991. Birkh\u00e4user Boston."},{"key":"9453_CR47","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-1-4612-0441-1_14","volume-title":"Effective Methods in Algebraic Geometry","author":"YN Lakshman","year":"1991","unstructured":"Y.\u00a0N.\u00a0Lakshman and D.\u00a0Lazard. On the complexity of zero-dimensional algebraic systems. In T.\u00a0Mora and C.\u00a0Traverso, editors, Effective Methods in Algebraic Geometry, pages 217\u2013225. Boston, MA, 1991. Birkh\u00e4user Boston."},{"key":"9453_CR48","doi-asserted-by":"crossref","unstructured":"D.\u00a0Lazard. Gr\u00f6bner bases, Gaussian elimination and resolution of systems of algebraic equations. In J.\u00a0A.\u00a0Hulzen, editor, Computer Algebra: EUROCAL\u201983, European Computer Algebra Conference London, England, March 28\u201330, 1983 Proceedings, pages 146\u2013156. Springer Berlin Heidelberg, 1983.","DOI":"10.1007\/3-540-12868-9_99"},{"key":"9453_CR49","doi-asserted-by":"crossref","unstructured":"F.\u00a0Le Gall. Powers of tensors and fast matrix multiplication. In K.\u00a0Nabeshima, editor, ISSAC\u201914: International Symposium on Symbolic and Algebraic Computation, pages 296\u2013303. New York, NY, USA, 2014. ACM.","DOI":"10.1145\/2608628.2608664"},{"issue":"4","key":"9453_CR50","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/S0885-064X(03)00031-1","volume":"19","author":"G Lecerf","year":"2003","unstructured":"G.\u00a0Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. J.\u00a0Complexity, 19(4):564\u2013596, 2003.","journal-title":"J. Complexity"},{"key":"9453_CR51","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.jsc.2018.04.017","volume":"92","author":"G Lecerf","year":"2019","unstructured":"G.\u00a0Lecerf. On the complexity of the Lickteig\u2013Roy subresultant algorithm. J.\u00a0Symbolic Comput., 92:243\u2013268, 2019.","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"9453_CR52","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1007\/BF01459805","volume":"299","author":"P Lelong","year":"1994","unstructured":"P.\u00a0Lelong. Mesure de Mahler et calcul de constantes universelles pour les polynomes de $$N$$ variables. Math. Ann., 299(1):673\u2013695, 1994.","journal-title":"Math. Ann."},{"key":"9453_CR53","unstructured":"H.\u00a0Matsumura. Commutative ring theory, volume\u00a08 of Cambridge Studies in Advanced Mathematics. Cambridge university press, 1989."},{"issue":"2","key":"9453_CR54","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1023\/A:1017543728036","volume":"126","author":"D McKinnon","year":"2001","unstructured":"D.\u00a0McKinnon. An arithmetic analogue of Bezout\u2019s theorem. Compos. Math., 126(2):147\u2013155, 2001.","journal-title":"Compos. Math."},{"key":"9453_CR55","unstructured":"J.\u00a0M.\u00a0McNamee and V.\u00a0Y.\u00a0Pan. Numerical Methods for Roots of Polynomials, Part\u00a0II, volume\u00a016 of Studies in Computational Mathematics. Elsevier, 2013."},{"issue":"2","key":"9453_CR56","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1137\/S0097539701385168","volume":"32","author":"B Mourrain","year":"2003","unstructured":"B.\u00a0Mourrain, V.\u00a0Y.\u00a0Pan, and O.\u00a0Ruatta. Accelerated solution of multivariate polynomial systems of equations. SIAM J.\u00a0Comput., 32(2):435\u2013454, 2003.","journal-title":"SIAM J. Comput."},{"key":"9453_CR57","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mourrain and Ph.\u00a0Tr\u00e9buchet. Solving projective complete intersection faster. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201900, pages 234\u2013241. New York, NY, USA, 2000. ACM.","DOI":"10.1145\/345542.345642"},{"key":"9453_CR58","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mourrain and Ph.\u00a0Tr\u00e9buchet. Generalized normal forms and polynomial system solving. In Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201905, pages 253\u2013260. New York, NY, USA, 2005. ACM.","DOI":"10.1145\/1073884.1073920"},{"key":"9453_CR59","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mourrain and Ph.\u00a0Tr\u00e9buchet. Border basis representation of a general quotient algebra. In Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201912, pages 265\u2013272. New York, NY, USA, 2012. ACM.","DOI":"10.1145\/2442829.2442868"},{"key":"9453_CR60","doi-asserted-by":"crossref","unstructured":"A.\u00a0K.\u00a0Narayanan. Fast computation of isomorphisms between finite fields using elliptic curves. In L.\u00a0Budaghyan and F.\u00a0Rodr\u00edguez-Henr\u00edquez, editors, Arithmetic of Finite Fields. 7th International Workshop, WAIFI 2018, Bergen, Norway, June 14\u201316, 2018, Revised Selected Papers, volume 11321 of Lecture Notes in Comput. Sci., pages 74\u201391. Springer, Cham, 2018.","DOI":"10.1007\/978-3-030-05153-2_4"},{"key":"9453_CR61","unstructured":"C.\u00a0H.\u00a0Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"issue":"1","key":"9453_CR62","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01446571","volume":"289","author":"P Philippon","year":"1991","unstructured":"P.\u00a0Philippon. Sur des hauteurs alternatives. I. Math. Ann., 289(1):255\u2013283, 1991.","journal-title":"Math. Ann."},{"key":"9453_CR63","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.jsc.2012.05.008","volume":"50","author":"A Poteaux","year":"2013","unstructured":"A.\u00a0Poteaux and \u00c9.\u00a0Schost. On the complexity of computing with zero-dimensional triangular sets. J.\u00a0Symbolic Comput., 50:110\u2013138, 2013.","journal-title":"J. Symbolic Comput."},{"issue":"2","key":"9453_CR64","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00289520","volume":"1","author":"A Sch\u00f6nhage","year":"1971","unstructured":"A.\u00a0Sch\u00f6nhage. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica, 1(2):139\u2013144, 1971.","journal-title":"Acta Informatica"},{"key":"9453_CR65","volume-title":"Fast algorithms: A multitape Turing machine implementation","author":"A Sch\u00f6nhage","year":"1994","unstructured":"A.\u00a0Sch\u00f6nhage, A.\u00a0F.\u00a0W.\u00a0Grotefeld, and E.\u00a0Vetter. Fast algorithms: A multitape Turing machine implementation. B.\u00a0I. Wissenschaftsverlag, Mannheim, 1994."},{"issue":"4","key":"9453_CR66","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"J.\u00a0T.\u00a0Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J.\u00a0ACM, 27(4):701\u2013717, 1980.","journal-title":"J. ACM"},{"issue":"189","key":"9453_CR67","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1090\/S0025-5718-1990-0993933-0","volume":"54","author":"V Shoup","year":"1990","unstructured":"V.\u00a0Shoup. New algorithms for finding irreducible polynomials over finite fields. Math. Comp., 54(189):435\u2013447, 1990.","journal-title":"Math. Comp."},{"key":"9453_CR68","doi-asserted-by":"crossref","unstructured":"P.\u00a0S.\u00a0Wang. A p-adic algorithm for univariate partial fractions. In Proceedings of the Fourth ACM Symposium on Symbolic and Algebraic Computation, SYMSAC \u201981, pages 212\u2013217. New York, NY, USA, 1981. ACM.","DOI":"10.1145\/800206.806398"},{"key":"9453_CR69","doi-asserted-by":"crossref","unstructured":"R.\u00a0Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM\u2019 79, number\u00a072 in Lect. Notes Comput. Sci., pages 216\u2013226. Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09453-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-020-09453-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09453-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:19:34Z","timestamp":1616113174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-020-09453-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,19]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["9453"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09453-0","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,19]]},"assertion":[{"value":"8 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}