Computing the structure of a finite abelian group
HTML articles powered by AMS MathViewer
- by Johannes Buchmann and Arthur Schmidt;
- Math. Comp. 74 (2005), 2017-2026
- DOI: https://doi.org/10.1090/S0025-5718-05-01740-0
- Published electronically: March 8, 2005
- PDF | Request permission
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}(|M|\sqrt {|G|})$ group operations and stores $\operatorname {O}(\sqrt {|G|})$ group elements.References
- Johannes Buchmann, Michael J. Jacobson Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Math. Comp. 66 (1997), no. 220, 1663–1687. MR 1432126, DOI 10.1090/S0025-5718-97-00880-6
- James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI 10.1137/0220067
- David C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Math. Comp. 69 (2000), no. 230, 767–773. MR 1653994, DOI 10.1090/S0025-5718-99-01141-2
Bibliographic 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
- Received by editor(s): April 23, 2003
- Received by editor(s) in revised form: August 2, 2004
- Published electronically: March 8, 2005
- © Copyright 2005 American Mathematical Society
- 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
- MathSciNet review: 2164109