{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:38:37Z","timestamp":1776785917122,"version":"3.51.2"},"reference-count":62,"publisher":"American Mathematical Society (AMS)","issue":"256","license":[{"start":{"date-parts":[[2007,7,20]],"date-time":"2007-07-20T00:00:00Z","timestamp":1184889600000},"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>We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the B\u00e9zout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.<\/p>","DOI":"10.1090\/s0025-5718-06-01878-3","type":"journal-article","created":{"date-parts":[[2006,8,16]],"date-time":"2006-08-16T10:28:45Z","timestamp":1155724125000},"page":"2049-2085","source":"Crossref","is-referenced-by-count":11,"title":["Fast computation of a rational point of a variety over a finite field"],"prefix":"10.1090","volume":"75","author":[{"given":"Antonio","family":"Cafure","sequence":"first","affiliation":[]},{"given":"Guillermo","family":"Matera","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2006,7,20]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-0348-9104-2_1","article-title":"Zeros, multiplicities, and idempotents for zero-dimensional systems","author":"Alonso, M.-E.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3764352744"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1006\/jcom.1997.0432","article-title":"Polar varieties, real equation solving, and data structures: the hypersurface case","volume":"13","author":"Bank, B.","year":"1997","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/PL00004896","article-title":"Polar varieties and efficient real elimination","volume":"238","author":"Bank, B.","year":"2001","journal-title":"Math. Z.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5874","issn-type":"print"},{"issue":"5","key":"4","first-page":"519","article-title":"Generalized polar varieties and an efficient real elimination procedure","volume":"40","author":"Bank, Bernd","year":"2004","journal-title":"Kybernetika (Prague)","ISSN":"https:\/\/id.crossref.org\/issn\/0023-5954","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.jco.2004.10.001","article-title":"Generalized polar varieties: geometry and algorithms","volume":"21","author":"Bank, B.","year":"2005","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"6","series-title":"Progress in Theoretical Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and matrix computations. Vol. 1","author":"Bini, Dario","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0817637869"},{"key":"7","doi-asserted-by":"crossref","unstructured":"A. Borodin, Time space tradeoffs (getting closer to the barriers?), 4th International Symposium on Algorithms and Computation, ISAAC \u201993, Hong Kong, December 15-17, 1993 (Berlin), Lecture Notes in Comput. Sci., vol. 762, Springer, 1993, pp. 209\u2013220.","DOI":"10.1007\/3-540-57568-5_251"},{"key":"8","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","volume":"315","author":"B\u00fcrgisser, Peter","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540605827"},{"key":"9","doi-asserted-by":"crossref","unstructured":"A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl., 12 (2006), no. 2, 155\u2013185.","DOI":"10.1016\/j.ffa.2005.03.003"},{"issue":"4","key":"10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10208-002-0065-7","article-title":"The hardness of polynomial equation solving","volume":"3","author":"Castro, D.","year":"2003","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"11","unstructured":"A.L. Chistov and D.Y. Grigoriev, Subexponential time solving systems of algebraic equations. I, II, LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad, 1983."},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","article-title":"Efficient algorithms for solving overdefined systems of multivariate polynomial equations","author":"Courtois, Nicolas","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540675175"},{"key":"13","series-title":"Undergraduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2181-2","volume-title":"Ideals, varieties, and algorithms","author":"Cox, David","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/038797847X"},{"key":"14","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"},{"key":"15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-662-03891-8_10","article-title":"Gr\u00f6bner bases for codes","author":"de Boer, Mario","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540634800"},{"key":"16","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5350-1","volume-title":"Commutative algebra","volume":"150","author":"Eisenbud, David","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942688"},{"key":"17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (\ud835\udc39\u2085)","author":"Faug\u00e8re, Jean-Charles","year":"2002"},{"key":"18","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02421-8","volume-title":"Intersection theory","volume":"2","author":"Fulton, William","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/3540121765"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-51082-6_83","article-title":"Algebraic solution of systems of polynomial equations using Groebner bases","author":"Gianni, Patrizia","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/3540510826"},{"key":"20","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0022-4049(97)00015-7","article-title":"Lower bounds for Diophantine approximations","volume":"117\/118","author":"Giusti, M.","year":"1997","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"issue":"1-3","key":"21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0022-4049(96)00099-0","article-title":"Straight-line programs in geometric elimination theory","volume":"124","author":"Giusti, M.","year":"1998","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-60114-7_16","article-title":"When polynomial equation systems can be \u201csolved\u201d fast?","author":"Giusti, M.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540601147"},{"issue":"11","key":"23","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1016\/S0764-4442(97)83558-6","article-title":"Le r\u00f4le des structures de donn\u00e9es dans les probl\u00e8mes d\u2019\u00e9limination","volume":"325","author":"Giusti, Marc","year":"1997","journal-title":"C. R. Acad. Sci. Paris S\\'{e}r. I Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0764-4442","issn-type":"print"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/BF01200407","article-title":"On the efficiency of effective Nullstellens\u00e4tze","volume":"3","author":"Giusti, Marc","year":"1993","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","article-title":"A Gr\u00f6bner free alternative for polynomial system solving","volume":"17","author":"Giusti, Marc","year":"2001","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","article-title":"Definability and fast quantifier elimination in algebraically closed fields","volume":"24","author":"Heintz, Joos","year":"1983","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"27","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51082-6","volume-title":"Applied algebra, algebraic algorithms and error-correcting codes","volume":"356","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/3540510826"},{"issue":"1","key":"28","first-page":"37","article-title":"The intrinsic complexity of parametric elimination methods","volume":"1","author":"Heintz, J.","year":"1998","journal-title":"Electron. J. SADIO"},{"issue":"4","key":"29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s002000000046","article-title":"On the time-space complexity of geometric elimination procedures","volume":"11","author":"Heintz, Joos","year":"2001","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"3","key":"30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s000370050029","article-title":"Solvability of systems of polynomial congruences modulo a large prime","volume":"8","author":"Huang, Ming-Deh","year":"1999","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"1","key":"31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1006\/jagm.2000.1098","article-title":"Extended Hilbert irreducibility and its applications","volume":"37","author":"Huang, Ming-Deh","year":"2000","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","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","isbn-type":"print","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-48405-1_2","article-title":"Cryptanalysis of the HFE public key cryptosystem by relinearization","author":"Kipnis, Aviad","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540663479"},{"key":"34","isbn-type":"print","first-page":"193","article-title":"A computational method for Diophantine approximation","author":"Krick, T.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3764352744"},{"key":"35","doi-asserted-by":"crossref","unstructured":"L. Kronecker, Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen, J. Reine Angew. Math. 92 (1882), 1\u2013122.","DOI":"10.1515\/crll.1882.92.1"},{"key":"36","isbn-type":"print","volume-title":"Introduction to commutative algebra and algebraic geometry","author":"Kunz, Ernst","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3764330651"},{"issue":"3","key":"37","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s102080010026","article-title":"Quadratic Newton iteration for systems with multiplicity","volume":"2","author":"Lecerf, G.","year":"2002","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"4","key":"38","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/S0885-064X(03)00031-1","article-title":"Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers","volume":"19","author":"Lecerf, Gr\u00e9goire","year":"2003","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"39","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0201135191"},{"key":"40","series-title":"Undergraduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6465-2","volume-title":"Applied abstract algebra","author":"Lidl, Rudolf","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/038796035X"},{"key":"41","series-title":"Cambridge Mathematical Library","isbn-type":"print","volume-title":"The algebraic theory of modular systems","author":"Macaulay, F. S.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0521455626"},{"key":"42","series-title":"Mathematics Lecture Note Series","isbn-type":"print","volume-title":"Commutative algebra","volume":"56","author":"Matsumura, Hideyuki","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0805370269","edition":"2"},{"key":"43","unstructured":"J.E. Morais, Resoluci\u00f3n eficaz de sistemas de ecuaciones polinomiales, Ph.D. thesis, Universidad de Cantabria, Santander, Spain, 1997."},{"key":"44","series-title":"Classics in Mathematics","isbn-type":"print","volume-title":"Algebraic geometry. I","author":"Mumford, David","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586571"},{"key":"45","isbn-type":"print","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-60114-7_4","article-title":"How lower and upper complexity bounds meet in elimination theory","author":"Pardo, Luis M.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540601147"},{"issue":"5","key":"46","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s002000050114","article-title":"Solving zero-dimensional systems through the rational univariate representation","volume":"9","author":"Rouillier, Fabrice","year":"1999","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"key":"47","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Band 4","volume-title":"M\\'{e}thodes d'alg\\`ebre abstraite en g\\'{e}om\\'{e}trie alg\\'{e}brique","author":"Samuel, Pierre","year":"1967"},{"key":"48","unstructured":"J.E. Savage, Models of computation. Exploring the power of computing, Addison-Wesley, Reading, Massachussets, 1998."},{"key":"49","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/0022-314X(74)90043-2","article-title":"A lower bound for the number of solutions of equations over finite fields","volume":"6","author":"Schmidt, Wolfgang M.","year":"1974","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"50","series-title":"Lecture Notes in Mathematics, Vol. 536","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0080437","volume-title":"Equations over finite fields. An elementary approach","author":"Schmidt, Wolfgang M.","year":"1976"},{"issue":"5","key":"51","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00200-002-0109-x","article-title":"Computing parametric geometric resolutions","volume":"13","author":"Schost, \u00c9ric","year":"2003","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"4","key":"52","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":"53","series-title":"Springer Study Edition","volume-title":"Basic algebraic geometry","author":"Shafarevich, I. R.","year":"1977"},{"key":"54","isbn-type":"print","volume-title":"Basic algebraic geometry. 1","author":"Shafarevich, Igor R.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540548122","edition":"2"},{"key":"55","isbn-type":"print","first-page":"633","article-title":"Algebraic complexity theory","author":"Strassen, Volker","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"56","isbn-type":"print","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BFb0016236","article-title":"Parallel arithmetic computations: a survey","author":"von zur Gathen, Joachim","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/3540167838"},{"key":"57","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"issue":"1","key":"58","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF01202042","article-title":"Counting curves and their projections","volume":"6","author":"von zur Gathen, Joachim","year":"1996","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"6","key":"59","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S0097539799351018","article-title":"Finding points on curves over finite fields","volume":"32","author":"von zur Gathen, Joachim","year":"2003","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"60","series-title":"Publications de l'Institut de Math\\'{e}matiques de l'Universit\\'{e} de Strasbourg [Publications of the Mathematical Institute of the University of Strasbourg]","volume-title":"Sur les courbes alg\\'{e}briques et les vari\\'{e}t\\'{e}s qui s'en d\\'{e}duisent","volume":"7","author":"Weil, Andr\u00e9","year":"1948"},{"key":"61","series-title":"Classics in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61991-5","volume-title":"Algebraic surfaces","author":"Zariski, Oscar","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/354058658X"},{"key":"62","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\/2006-75-256\/S0025-5718-06-01878-3\/S0025-5718-06-01878-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-256\/S0025-5718-06-01878-3\/S0025-5718-06-01878-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:41:43Z","timestamp":1776782503000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-256\/S0025-5718-06-01878-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,20]]},"references-count":62,"journal-issue":{"issue":"256","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["S0025-5718-06-01878-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01878-3","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":[[2006,7,20]]}}}