{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:14:27Z","timestamp":1776863667992,"version":"3.51.2"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,7,6]],"date-time":"2018-07-06T00:00:00Z","timestamp":1530835200000},"content-version":"tdm","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":[[2019,6]]},"DOI":"10.1007\/s10208-018-9392-1","type":"journal-article","created":{"date-parts":[[2018,7,6]],"date-time":"2018-07-06T17:24:52Z","timestamp":1530897892000},"page":"591-621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Improved Complexity Bounds for Counting Points on Hyperelliptic Curves"],"prefix":"10.1007","volume":"19","author":[{"given":"Simon","family":"Abelard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierrick","family":"Gaudry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre-Jean","family":"Spaenlehauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,6]]},"reference":[{"issue":"3","key":"9392_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jsco.2001.0470","volume":"32","author":"LM Adleman","year":"2001","unstructured":"Adleman, L.M., Huang, M.D.: Counting points on curves and Abelian varieties over finite fields. Journal of Symbolic Computation 32(3), 171\u2013189 (2001)","journal-title":"Journal of Symbolic Computation"},{"issue":"201","key":"9392_CR2","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1090\/S0025-5718-1993-1140645-1","volume":"60","author":"AOL Atkin","year":"1993","unstructured":"Atkin, A.O.L., Morain, F.: Finding suitable curves for the elliptic curve method of factorization. Mathematics of Computation 60(201), 399\u2013405 (1993)","journal-title":"Mathematics of Computation"},{"issue":"256","key":"9392_CR3","doi-asserted-by":"publisher","first-page":"2049","DOI":"10.1090\/S0025-5718-06-01878-3","volume":"75","author":"A Cafure","year":"2006","unstructured":"Cafure, A., Matera, G.: Fast computation of a rational point of a variety over a finite field. Mathematics of Computation 75(256), 2049\u20132085 (2006)","journal-title":"Mathematics of Computation"},{"issue":"177","key":"9392_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1090\/S0025-5718-1987-0866101-0","volume":"48","author":"DG Cantor","year":"1987","unstructured":"Cantor, D.G.: Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation 48(177), 95\u2013101 (1987)","journal-title":"Mathematics of Computation"},{"key":"9392_CR5","first-page":"91","volume":"447","author":"DG Cantor","year":"1994","unstructured":"Cantor, D.G.: On the analogue of the division polynomials for hyperelliptic curves. Journal fur die reine und angewandte Mathematik 447, 91\u2013146 (1994)","journal-title":"Journal fur die reine und angewandte Mathematik"},{"key":"9392_CR6","doi-asserted-by":"publisher","DOI":"10.1201\/9781420034981","volume-title":"Handbook of elliptic and hyperelliptic curve cryptography","author":"H Cohen","year":"2005","unstructured":"Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (2005) Handbook of elliptic and hyperelliptic curve cryptography. CRC press, Boca Raton"},{"key":"9392_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of public key cryptography","author":"SD Galbraith","year":"2012","unstructured":"Galbraith, S.D. (2012) Mathematics of public key cryptography. Cambridge University Press, Cambridge"},{"key":"9392_CR8","doi-asserted-by":"crossref","unstructured":"Gaudry, P., Kohel, D.R., Smith, B.A.: Counting points on genus 2 curves with real multiplication. In: ASIACRYPT 2011, LNCS, vol. 7073, pp. 504\u2013519. Springer (2011)","DOI":"10.1007\/978-3-642-25385-0_27"},{"issue":"4","key":"9392_CR9","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.jsc.2011.09.003","volume":"47","author":"P Gaudry","year":"2012","unstructured":"Gaudry, P., Schost, \u00c9.: Genus 2 point counting over prime fields. Journal of Symbolic Computation 47(4), 368\u2013400 (2012)","journal-title":"Journal of Symbolic Computation"},{"issue":"1","key":"9392_CR10","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M Giusti","year":"2001","unstructured":"Giusti, M., Lecerf, G., Salvy, B.: A Gr\u00f6bner free alternative for polynomial system solving. Journal of complexity 17(1), 154\u2013211 (2001)","journal-title":"Journal of complexity"},{"key":"9392_CR11","doi-asserted-by":"publisher","first-page":"1379","DOI":"10.1112\/plms\/pdv056","volume":"111","author":"D Harvey","year":"2015","unstructured":"Harvey, D.: Computing zeta functions of arithmetic schemes. Proceedings of the London Mathematical Society 111, 1379\u20131401 (2015)","journal-title":"Proceedings of the London Mathematical Society"},{"issue":"3","key":"9392_CR12","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J Heintz","year":"1983","unstructured":"Heintz, J.: Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science 24(3), 239\u2013277 (1983)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9392_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jsco.1997.0164","volume":"25","author":"MD Huang","year":"1998","unstructured":"Huang, M.D., Ierardi, D.: Counting points on curves over finite fields. Journal of Symbolic Computation 25(1), 1\u201321 (1998)","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"9392_CR14","first-page":"323","volume":"16","author":"KS Kedlaya","year":"2001","unstructured":"Kedlaya, K.S.: Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. Journal of the Ramanujan mathematical society 16(4), 323\u2013338 (2001)","journal-title":"Journal of the Ramanujan mathematical society"},{"key":"9392_CR15","unstructured":"Kleiman, S.L.: Bertini and his two fundamental theorems. arXiv:alg-geom\/9704018v1 (1997)"},{"issue":"3","key":"9392_CR16","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1112\/S0024611503014461","volume":"88","author":"AGB Lauder","year":"2004","unstructured":"Lauder, A.G.B.: Deformation theory and the computation of zeta functions. Proceedings of the London Mathematical Society 88(3), 565\u2013602 (2004)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"9392_CR17","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1017\/9781139049801.019","volume-title":"Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Mathematical Sciences Research Institute Publications","author":"AGB Lauder","year":"2008","unstructured":"Lauder, A.G.B., Wan, D.: Counting points on varieties over finite fields of small characteristic. In: J.P. Buhler, P.\u00a0Stevenhagen (eds.) Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Mathematical Sciences Research Institute Publications, pp. 579\u2013612. Cambridge University Press, Cambridge (2008)"},{"key":"9392_CR18","doi-asserted-by":"crossref","unstructured":"Lorenzini, D.: An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol.\u00a09. American Mathematical Soc (1996)","DOI":"10.1090\/gsm\/009"},{"key":"9392_CR19","volume-title":"Abelian varieties","author":"D Mumford","year":"1974","unstructured":"Mumford, D.: Abelian varieties. Oxford University Press, Oxford (1974)"},{"issue":"192","key":"9392_CR20","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1090\/S0025-5718-1990-1035941-X","volume":"55","author":"J Pila","year":"1990","unstructured":"Pila, J.: Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation 55(192), 745\u2013763 (1990)","journal-title":"Mathematics of Computation"},{"key":"9392_CR21","unstructured":"Pila, J.: Counting points on curves over families in polynomial time. arXiv:math\/0504570v1 (2005)"},{"issue":"6","key":"9392_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2996450","volume":"63","author":"M Safey El Din","year":"2017","unstructured":"Safey El\u00a0Din, M., Schost, \u00c9.: A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Journal of the ACM 63(6), 1\u2013 48 (2017)","journal-title":"Journal of the ACM"},{"issue":"4","key":"9392_CR23","first-page":"247","volume":"15","author":"T Satoh","year":"2000","unstructured":"Satoh, T.: The canonical lift of an ordinary elliptic curve over a finite field and its point counting. Journal of the Ramanujan mathematical society 15(4), 247\u2013270 (2000)","journal-title":"Journal of the Ramanujan mathematical society"},{"issue":"170","key":"9392_CR24","first-page":"483","volume":"44","author":"R Schoof","year":"1985","unstructured":"Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of Computation 44(170), 483\u2013494 (1985)","journal-title":"Mathematics of Computation"},{"key":"9392_CR25","doi-asserted-by":"publisher","DOI":"10.1142\/5763","volume-title":"The numerical solution of systems of polynomials arising in engineering and science","author":"AJ Sommese","year":"2005","unstructured":"Sommese, A.J., Wampler\u00a0II, C.W. (2005) The numerical solution of systems of polynomials arising in engineering and science. World Scientific, Singapore"},{"key":"9392_CR26","volume-title":"Introduction to analytic and probabilistic number theory","author":"G Tenenbaum","year":"1995","unstructured":"Tenenbaum, G. (1995) Introduction to analytic and probabilistic number theory. Cambridge university press, Cambridge"},{"key":"9392_CR27","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1090\/mcom\/2996","volume":"85","author":"J Tuitman","year":"2016","unstructured":"Tuitman, J.: Counting points on curves using a map to $${P}^1$$ P 1 . Mathematics of Computation 85, 961\u2013981 (2016)","journal-title":"Mathematics of Computation"},{"key":"9392_CR28","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.ffa.2016.12.008","volume":"45","author":"J Tuitman","year":"2017","unstructured":"Tuitman, J.: Finite Fields and Their Applications . Finite Fields and Their Applications 45, 301,322 (2017)","journal-title":"Finite Fields and Their Applications"},{"key":"9392_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern computer algebra","author":"J Zur Gathen Von","year":"2013","unstructured":"Von Zur\u00a0Gathen, J., Gerhard, J. (2013) Modern computer algebra. Cambridge university press, Cambridge","edition":"Third"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-018-9392-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-018-9392-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-018-9392-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T16:40:12Z","timestamp":1751733612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-018-9392-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,6]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["9392"],"URL":"https:\/\/doi.org\/10.1007\/s10208-018-9392-1","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,6]]},"assertion":[{"value":"9 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}