{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:38:44Z","timestamp":1776728324576,"version":"3.51.2"},"reference-count":33,"publisher":"American Mathematical Society (AMS)","issue":"239","license":[{"start":{"date-parts":[[2002,10,4]],"date-time":"2002-10-04T00:00:00Z","timestamp":1033689600000},"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>Recently, several algorithms have been suggested for solving the discrete logarithm problem in the Jacobians of high-genus hyperelliptic curves over finite fields. Some of them have a provable subexponential running time and are using the fact that smooth reduced ideals are sufficiently dense. We explicitly show how these density results can be derived. All proofs are purely combinatorial and do not exploit analytic properties of generating functions.<\/p>","DOI":"10.1090\/s0025-5718-01-01352-7","type":"journal-article","created":{"date-parts":[[2002,9,20]],"date-time":"2002-09-20T15:46:54Z","timestamp":1032536814000},"page":"1219-1230","source":"Crossref","is-referenced-by-count":4,"title":["Smooth ideals in hyperelliptic function fields"],"prefix":"10.1090","volume":"71","author":[{"given":"Andreas","family":"Enge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Stein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2001,10,4]]},"reference":[{"issue":"203","key":"1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2152932","article-title":"A subexponential algorithm for discrete logarithms over all finite fields","volume":"61","author":"Adleman, Leonard M.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"2","doi-asserted-by":"publisher","first-page":"549","DOI":"10.2307\/1968939","article-title":"Transformationen von algebraischem Typ","volume":"40","author":"Kober, Hermann","year":"1939","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"3","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58691-1","volume-title":"Algorithmic number theory","volume":"877","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[Art24] E. Artin. Quadratische K\u00f6rper im Gebiete der h\u00f6heren Kongruenzen I, II. Mathematische Zeitschrift, 19:153\u2013206, 1924.","DOI":"10.1007\/BF01181074"},{"key":"5","unstructured":"[Bau98] Mark Bauer. A subexponential algorithm for solving the discrete logarithm problem in the Jacobian of high genus hyperelliptic curves over arbitrary finite fields. Preprint, 1998."},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1090\/amsip\/007\/11","article-title":"Rigorous discrete logarithm computations in finite fields via smooth polynomials","author":"Bender, Renet Lovorn","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"key":"7","series-title":"AMS\/IP Studies in Advanced Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/amsip\/007","volume-title":"Computational perspectives on number theory","volume":"7","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"key":"8","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054849","volume-title":"Algorithmic number theory","volume":"1423","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646574"},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.4064\/aa-48-2-145-165","article-title":"Th\u00e9or\u00e8mes de densit\u00e9 dans \ud835\udc39_{\ud835\udc5e}[\ud835\udc4b]","volume":"48","author":"Car, Mireille","year":"1987","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"6","key":"10","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/tit.1976.1055638","article-title":"New directions in cryptography","volume":"IT-22","author":"Diffie, Whitfield","year":"1976","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"11","unstructured":"[EG00] Andreas Enge and Pierrick Gaudry. A general framework for subexponential discrete logarithm algorithms. Research Report LIX\/RR\/00\/04, LIX, June 2000. Available at http:\/\/www.math.uni-augsburg.de\/\u02dcenge\/vorabdrucke\/subexp.ps.gz."},{"key":"12","unstructured":"[Eng99] Andreas Enge. Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time. Combinatorics and Optimization Research Report CORR 99-04, University of Waterloo, February 1999. Available at http:\/\/cacr.math.uwaterloo.ca\/techreports\/1999\/corr99-04.ps; to appear in Mathematics of Computation."},{"key":"13","unstructured":"[He{\\ss}99] Florian He\u00df. Zur Divisorenklassengruppenberechnung in globalen Funktionenk\u00f6rpern. PhD thesis, Technische Universit\u00e4t Berlin, 1999."},{"key":"14","series-title":"North-Holland Mathematical Library, Vol. 12","volume-title":"Abstract analytic number theory","author":"Knopfmacher, John","year":"1975"},{"issue":"177","key":"15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.2307\/2007884","article-title":"Elliptic curve cryptosystems","volume":"48","author":"Koblitz, Neal","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","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":"4","key":"17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/BF00970673","article-title":"Remarks on elements of semigroups that are free of large prime factors","volume":"32","author":"Manstavichyus, E.","year":"1992","journal-title":"Liet. Mat. Rink.","ISSN":"https:\/\/id.crossref.org\/issn\/0132-2818","issn-type":"print"},{"key":"18","isbn-type":"print","first-page":"135","article-title":"Semigroup elements free of large prime factors","author":"Manstavi\u010dius, E.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/9067640948"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-39799-X_31","article-title":"Use of elliptic curves in cryptography","author":"Miller, Victor S.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/3540164634"},{"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"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/BFb0054865","article-title":"An analytic approach to smooth polynomials over finite fields","author":"Panario, Daniel","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646574"},{"issue":"227","key":"22","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1090\/S0025-5718-99-01066-2","article-title":"Real and imaginary quadratic representations of hyperelliptic function fields","volume":"68","author":"Paulus, Sachar","year":"1999","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"23","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest, R. L.","year":"1978","journal-title":"Comm. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"print"},{"issue":"178","key":"24","doi-asserted-by":"publisher","first-page":"757","DOI":"10.2307\/2007842","article-title":"A probabilistic factorization algorithm with quadratic forms of negative discriminant","volume":"48","author":"Seysen, Martin","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"25","isbn-type":"print","volume-title":"New trends in probability and statistics. Vol. 2","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/9067640948"},{"key":"26","unstructured":"[Sou98] K. Soundararajan. Smooth polynomials: Analogies and asymptotics. Preprint, July 1998."},{"issue":"1-2","key":"27","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF00125081","article-title":"Key-exchange in real quadratic congruence function fields","volume":"7","author":"Scheidler, R.","year":"1996","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"#cr-split#-28.1","unstructured":"[ST99] A. Stein and E. Teske. Explicit bounds and heuristics on class numbers in hyperelliptic function fields. Technical Report CORR 99-26, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, 1999"},{"key":"#cr-split#-28.2","unstructured":"Math. Comp., posted on October 4, 2001, PII S0025-5718(01)01385-0 (to appear in print)."},{"issue":"1","key":"29","doi-asserted-by":"publisher","first-page":"75","DOI":"10.5802\/jtnb.191","article-title":"Equivalences between elliptic curves and real quadratic congruence function fields","volume":"9","author":"Stein, Andreas","year":"1997","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"30","series-title":"Universitext","isbn-type":"print","volume-title":"Algebraic function fields and codes","author":"Stichtenoth, Henning","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540564896"},{"issue":"2","key":"31","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1080\/10586458.1999.10504394","article-title":"Some methods for evaluating the regulator of a real quadratic function field","volume":"8","author":"Stein, Andreas","year":"1999","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"32","isbn-type":"print","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/BFb0054897","article-title":"The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2","author":"Zuccherato, Robert J.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646574"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01352-7\/S0025-5718-01-01352-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01352-7\/S0025-5718-01-01352-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:00:40Z","timestamp":1776726040000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01352-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,10,4]]},"references-count":33,"journal-issue":{"issue":"239","published-print":{"date-parts":[[2002,7]]}},"alternative-id":["S0025-5718-01-01352-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-01-01352-7","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":[[2001,10,4]]}}}