Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


A space efficient algorithm for group structure computation
HTML articles powered by AMS MathViewer

by Edlyn Teske PDF
Math. Comp. 67 (1998), 1637-1663 Request permission


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 $O(\sqrt {n})$ (with $n$ denoting the group order), and we explicitly determine the $O$-constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (1991): 11Y16
  • Retrieve articles in all journals with MSC (1991): 11Y16
Additional Information
  • Edlyn Teske
  • Affiliation: Technische Universität Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10 64283 Darmstadt Germany
  • Address at time of publication: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
  • Email:
  • Received by editor(s): February 7, 1997
  • Received by editor(s) in revised form: April 23, 1997
  • © Copyright 1998 American Mathematical Society
  • Journal: Math. Comp. 67 (1998), 1637-1663
  • MSC (1991): Primary 11Y16
  • DOI:
  • MathSciNet review: 1474658