Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing the structure of a finite abelian group


Authors: Johannes Buchmann and Arthur Schmidt
Journal: Math. Comp. 74 (2005), 2017-2026
MSC (2000): Primary 11Y16; Secondary 20C40, 20K02
DOI: https://doi.org/10.1090/S0025-5718-05-01740-0
Published electronically: March 8, 2005
MathSciNet review: 2164109
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present an algorithm that computes the structure of a finite abelian group $G$ from a generating system $M$. The algorithm executes $\operatorname{O}(\vert M\vert\sqrt{\vert G\vert})$ group operations and stores $\operatorname{O}(\sqrt{\vert G\vert})$ group elements.


References [Enhancements On Off] (What's this?)

  • [BJT97] J. Buchmann, M.J. Jacobson, Jr., and E. Teske, On some computational problems in finite abelian groups, Mathematics of Computation 66 (1997), 1663-1687. MR 1432126 (98a:11185)
  • [HM91] J.L. Hafner and K.S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM Journal on Computing 20 (1991), 1068-1083. MR 1135749 (93d:15021)
  • [Ter00] David C. Terr, A modification of Shanks' baby-step giant-step algorithm, Math. Comp. 69 (2000), no. 230, 767-773.MR 1653994 (2000i:20039)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 20C40, 20K02

Retrieve articles in all journals with MSC (2000): 11Y16, 20C40, 20K02


Additional Information

Johannes Buchmann
Affiliation: Technische Universität Darmstadt, Theoretische Informatik, Hochschulstr. 10, 64289 Darmstadt, Germany
Email: buchmann@cdc.informatik.tu-darmstadt.de

Arthur Schmidt
Affiliation: Technische Universität Darmstadt, Theoretische Informatik, Hochschulstr. 10, 64289 Darmstadt, Germany
Email: aschmidt@cdc.informatik.tu-darmstadt.de

DOI: https://doi.org/10.1090/S0025-5718-05-01740-0
Received by editor(s): April 23, 2003
Received by editor(s) in revised form: August 2, 2004
Published electronically: March 8, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society