{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:40:43Z","timestamp":1776840043055,"version":"3.51.2"},"reference-count":27,"publisher":"American Mathematical Society (AMS)","issue":"257","license":[{"start":{"date-parts":[[2007,10,4]],"date-time":"2007-10-04T00:00:00Z","timestamp":1191456000000},"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>In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard\u2019s Rho method even for rather small field sizes.<\/p>","DOI":"10.1090\/s0025-5718-06-01900-4","type":"journal-article","created":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T16:50:02Z","timestamp":1162399802000},"page":"475-492","source":"Crossref","is-referenced-by-count":67,"title":["A double large prime variation for small genus hyperelliptic index calculus"],"prefix":"10.1090","volume":"76","author":[{"given":"P.","family":"Gaudry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Thom\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Th\u00e9riault","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Diem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2006,10,4]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/3-540-58691-1_39","article-title":"A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields","author":"Adleman, Leonard M.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"2","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The design and analysis of computer algorithms","author":"Aho, Alfred V.","year":"1975"},{"issue":"177","key":"3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.2307\/2007876","article-title":"Computing in the Jacobian of a hyperelliptic curve","volume":"48","author":"Cantor, David G.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/aama.2001.0720","article-title":"The diameter of sparse random graphs","volume":"26","author":"Chung, Fan","year":"2001","journal-title":"Adv. in Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-8858","issn-type":"print"},{"issue":"205","key":"5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/2153413","article-title":"Solving homogeneous linear equations over \ud835\udc3a\ud835\udc39(2) via block Wiedemann algorithm","volume":"62","author":"Coppersmith, Don","year":"1994","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","isbn-type":"print","first-page":"17","article-title":"Algebraic groups and discrete logarithm","author":"Couveignes, Jean-Marc","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3110170469"},{"key":"7","doi-asserted-by":"crossref","unstructured":"C. Diem, Index calculus algorithm for plane curves of small degree, ANTS-VII (F. He\u00df, S. Pauli and M. Pohst, eds.), Lecture Notes in Comput. Sci., vol. 4076, Springer-Verlag, 2006, pp. 543\u2013557.","DOI":"10.1007\/11792086_38"},{"issue":"238","key":"8","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1090\/S0025-5718-01-01363-1","article-title":"Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time","volume":"71","author":"Enge, Andreas","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.4064\/aa102-1-6","article-title":"A general framework for subexponential discrete logarithm algorithms","volume":"102","author":"Enge, Andreas","year":"2002","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"1-3","key":"10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0012-365X(89)90087-3","article-title":"The first cycles in an evolving graph","volume":"75","author":"Flajolet, Philippe","year":"1989","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-45539-6_2","article-title":"An algorithm for solving the discrete log problem on hyperelliptic curves","author":"Gaudry, Pierrick","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540675175"},{"key":"12","unstructured":"\\bysame, Index calculus for abelian varieties and the elliptic curve discrete logarithm problem, Cryptology ePrint Archive: Report 2004\/073, 2004."},{"issue":"4","key":"13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1006\/jsco.2001.0513","article-title":"Computing Riemann-Roch spaces in algebraic function fields and related topics","volume":"33","author":"Hess, F.","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"14","unstructured":"\\bysame, Computing relations in divisor class groups of algebraic curves over finite fields, Preprint, 2004."},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jsco.1997.0164","article-title":"Counting points on curves over finite fields","volume":"25","author":"Huang, Ming-Deh","year":"1998","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF02252872","article-title":"Hyperelliptic cryptosystems","volume":"1","author":"Koblitz, Neal","year":"1989","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"208","key":"17","doi-asserted-by":"publisher","first-page":"785","DOI":"10.2307\/2153299","article-title":"Factoring with two large primes","volume":"63","author":"Lenstra, A. K.","year":"1994","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/3-540-45455-1_35","article-title":"MPQS with three large primes","author":"Leyland, Paul","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"19","series-title":"Algorithms and Computation in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03642-6","volume-title":"Algebraic aspects of cryptography","volume":"3","author":"Koblitz, Neal","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540634460"},{"issue":"226","key":"20","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1090\/S0025-5718-99-01040-6","article-title":"Computing discrete logarithms in real quadratic congruence function fields of large genus","volume":"68","author":"M\u00fcller, Volker","year":"1999","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"192","key":"21","doi-asserted-by":"publisher","first-page":"745","DOI":"10.2307\/2008445","article-title":"Frobenius maps of abelian varieties and finding roots of unity in finite fields","volume":"55","author":"Pila, J.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"22","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/tit.1978.1055817","article-title":"An improved algorithm for computing logarithms over \ud835\udc3a\ud835\udc39(\ud835\udc5d) and its cryptographic significance","volume":"IT-24","author":"Pohlig, Stephen C.","year":"1978","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-540-40061-5_5","article-title":"Index calculus attack for hyperelliptic curves of small genus","author":"Th\u00e9riault, Nicolas","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540205926"},{"issue":"5","key":"24","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1006\/jsco.2002.0533","article-title":"Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm","volume":"33","author":"Thom\u00e9, Emmanuel","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"25","unstructured":"\\bysame, Algorithmes de calcul de logarithme discret dans les corps finis, Th\u00e8se, \u00c9cole polytechnique, May, 2003."},{"key":"26","isbn-type":"print","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/3-540-58691-1_60","article-title":"Computing in the Jacobian of a plane algebraic curve","author":"Volcheck, Emil J.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"27","doi-asserted-by":"crossref","unstructured":"T. Wollinger, J. Pelzl, and C. Paar, Cantor versus Harley: Optimization and analysis of explicit formulae for hyperelliptic curve cryptosystem, Tech. report, Universit\u00e4t Bochum, 2004, Available at http:\/\/www.crypto.rub.de\/.","DOI":"10.1109\/TC.2005.109"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01900-4\/S0025-5718-06-01900-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01900-4\/S0025-5718-06-01900-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:46:58Z","timestamp":1776782818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01900-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,4]]},"references-count":27,"journal-issue":{"issue":"257","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0025-5718-06-01900-4"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01900-4","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,10,4]]}}}