×

Computing the structure of a finite Abelian group. (English) Zbl 1089.20032

The “structure” of a finite Abelian group is the decomposition as a direct product of cyclic groups. Calculating this structure can be hard if there are factors of high order – this happens for example with class groups in number theory.
Using the improved order algorithm of D. C. Terr [Math. Comput. 69, No. 230, 767-773 (2000; Zbl 0940.68038)] the authors improve on the complexity result of J. Buchmann, M. J. Jacobson jun. and E. Teske [Math. Comput. 66, No. 220, 1663-1687 (1997; Zbl 0894.11050)]. They prove an improved complexity bound of \(O(|M|\sqrt{|G|})\) group operations (where \(M\) is the number of generators) and storage of \(O(\sqrt{|G|}) \) group elements.
The paper is a pure complexity result and does not consider an implementation.

MSC:

20K01 Finite abelian groups
11Y16 Number-theoretic algorithms; complexity
20C40 Computational methods (representations of groups) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0894.11050
[2] James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068 – 1083. · Zbl 0738.68050 · doi:10.1137/0220067
[3] David C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Math. Comp. 69 (2000), no. 230, 767 – 773. · Zbl 0940.68038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.