Computing the structure of a finite abelian group (Q5315431)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2203631
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing the structure of a finite abelian group |
scientific article; zbMATH DE number 2203631 |
Statements
Computing the structure of a finite abelian group (English)
0 references
8 September 2005
0 references
algorithms
0 references
finite Abelian groups
0 references
numbers of generators
0 references
orders of elements
0 references
complexity bounds
0 references
0.8790725469589233
0 references
0.8782204389572144
0 references
0.8602227568626404
0 references
0.8483714461326599
0 references
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 \textit{D. C. Terr} [Math. Comput. 69, No. 230, 767-773 (2000; Zbl 0940.68038)] the authors improve on the complexity result of \textit{J. Buchmann, M. J. Jacobson} jun. and \textit{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.
0 references