{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:00:04Z","timestamp":1776844804462,"version":"3.51.2"},"reference-count":10,"publisher":"American Mathematical Society (AMS)","issue":"220","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present new algorithms for computing orders of elements, discrete logarithms, and structures of finite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly determine the\n \n \n \n O<\/mml:mi>\n O<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -constants and\n \n \n \n \n \u03a9\n \n <\/mml:mi>\n \\Omega<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our experimental results. Our algorithms are based on a modification of Shanks\u2019 baby-step giant-step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order.\n <\/p>","DOI":"10.1090\/s0025-5718-97-00880-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:13:45Z","timestamp":1027707225000},"page":"1663-1687","source":"Crossref","is-referenced-by-count":31,"title":["On some computational problems in finite abelian groups"],"prefix":"10.1090","volume":"66","author":[{"given":"Johannes","family":"Buchmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"Michael","family":"Jacobson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edlyn","family":"Teske","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[1997]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1090\/psapm\/048\/1314882","article-title":"Algorithms for quadratic orders","author":"Biehl, Ingrid","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821802917"},{"key":"2","unstructured":"J. Buchmann and S. Paulus, Algorithms for finite abelian groups, Extended abstract. To be published in the proceedings of NTAMCS 93."},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4542-1","volume-title":"Binary quadratic forms","author":"Buell, Duncan A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0387970371"},{"key":"4","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BFb0099440","article-title":"Heuristics on class groups of number fields","author":"Cohen, H.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/3540133569"},{"issue":"3","key":"6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1145\/66888.66892","article-title":"Residual Hermite normal form computations","volume":"15","author":"Domich, Paul D.","year":"1989","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"key":"7","unstructured":"J. Buchmann I. Biehl and T. Papanikolaou, LiDIA - a library for computational number theory, The LiDIA Group, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1995."},{"key":"8","doi-asserted-by":"crossref","unstructured":"A.K. Lenstra and H.W. Lenstra, Jr., Algorithms in number theory, Handbook of theoretical computer science (J. van Leeuwen, ed.), Elsevier Science Publishers, 1990, pp. 673\u2013715.","DOI":"10.1016\/B978-0-444-88071-0.50017-5"},{"key":"9","unstructured":"S. Paulus, Algorithmen f\u00fcr endliche abelsche Gruppen, Master\u2019s thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1992."},{"key":"10","first-page":"415","article-title":"Class number, a theory of factorization, and genera","author":"Shanks, Daniel","year":"1971"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1997-66-220\/S0025-5718-97-00880-6\/S0025-5718-97-00880-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1997-66-220\/S0025-5718-97-00880-6\/S0025-5718-97-00880-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:36:54Z","timestamp":1776721014000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1997-66-220\/S0025-5718-97-00880-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"references-count":10,"journal-issue":{"issue":"220","published-print":{"date-parts":[[1997,10]]}},"alternative-id":["S0025-5718-97-00880-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-97-00880-6","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":[[1997]]}}}