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

\n We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n O(\\sqrt {n})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (with\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n denoting the group order), 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. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.\n <\/p>","DOI":"10.1090\/s0025-5718-98-00968-5","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1637-1663","source":"Crossref","is-referenced-by-count":33,"title":["A space efficient algorithm for group structure computation"],"prefix":"10.1090","volume":"67","author":[{"given":"Edlyn","family":"Teske","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"issue":"220","key":"1","doi-asserted-by":"publisher","first-page":"1663","DOI":"10.1090\/S0025-5718-97-00880-6","article-title":"On some computational problems in finite abelian groups","volume":"66","author":"Buchmann, Johannes","year":"1997","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BF01933190","article-title":"An improved Monte Carlo factorization algorithm","volume":"20","author":"Brent, Richard P.","year":"1980","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"3","first-page":"10","article-title":"Sur les points singuliers des \u00e9quations diff\u00e9rentielles","volume":"209","author":"Rosenblatt, Alfred","year":"1939","journal-title":"C. R. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4036","issn-type":"print"},{"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","series-title":"Lecture Notes in Computer Science","isbn-type":"print","volume-title":"Advances in cryptology---EUROCRYPT '89","volume":"434","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/3540534334"},{"key":"6","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The art of computer programming. Volume 3","author":"Knuth, Donald E.","year":"1973"},{"key":"7","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The art of computer programming","author":"Knuth, Donald E.","year":"1975","edition":"2"},{"key":"8","unstructured":"[LiD96] LiDIA Group, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany. LiDIA - A library for computational number theory, Version 1.2, 1996."},{"issue":"167","key":"9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/2007414","article-title":"A Monte Carlo factoring algorithm with linear storage","volume":"43","author":"Schnorr, C.-P.","year":"1984","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","series-title":"Mathematical Centre Tracts","isbn-type":"print","volume-title":"Computational methods in number theory. Part II","volume":"155","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/9061962498"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1090\/psapm\/042\/1095551","article-title":"The discrete logarithm problem","author":"McCurley, Kevin S.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0821801554"},{"issue":"143","key":"12","doi-asserted-by":"publisher","first-page":"918","DOI":"10.2307\/2006496","article-title":"Monte Carlo methods for index computation (\ud835\udc5a\ud835\udc5c\ud835\udc51\ud835\udc5d)","volume":"32","author":"Pollard, J. M.","year":"1978","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"13","first-page":"10","article-title":"Sur les points singuliers des \u00e9quations diff\u00e9rentielles","volume":"209","author":"Rosenblatt, Alfred","year":"1939","journal-title":"C. R. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4036","issn-type":"print"},{"key":"14","first-page":"415","article-title":"Class number, a theory of factorization, and genera","author":"Shanks, Daniel","year":"1971"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[Sho96] V. Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology\u2013Eurocrypt \u201997, Lectures Notes in Computer Sci., Volume 1233, pp. 256\u2013266, Springer-Verlag, New York, 1997.","DOI":"10.1007\/3-540-69053-0_18"},{"key":"16","first-page":"65","article-title":"Generating random walks in groups","volume":"6","author":"Sattler, J.","year":"1985","journal-title":"Ann. Univ. Sci. Budapest. Sect. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0138-9491","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00968-5\/S0025-5718-98-00968-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00968-5\/S0025-5718-98-00968-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:51:58Z","timestamp":1776721918000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00968-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":16,"journal-issue":{"issue":"224","published-print":{"date-parts":[[1998,10]]}},"alternative-id":["S0025-5718-98-00968-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00968-5","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":[[1998]]}}}