Buchmann, Johannes; Jacobson, Michael J. jun.; Teske, Edlyn On some computational problems in finite abelian groups. (English) Zbl 0894.11050 Math. Comput. 66, No. 220, 1663-1687 (1997). Let \(G\) be a finite abelian group written multiplicatively. The order computation problem is, given an element \(g\in G\), compute the smallest positive integer \(x\) with \(g^x=1\). The discrete logarithm problem is, given elements \(g,d\in G\), determine if \(d\in \langle g \rangle\), and if so, compute an integer \(x\) such that \(g^x=d\). The structure problem is, given a generating set for \(G\), compute a list of positive integers \(m_1, \ldots, m_k\) with \(m_1>1\), \(m_i\mid m_{i+1}\) for \(1\leq i<k\), and an isomorphism \(\phi:G\rightarrow\mathbb Z/m_1\mathbb{Z}\times \cdots \times\mathbb Z/m_k\mathbb Z\). In this paper, the authors present algorithms for solving these three problems. All their algorithms are based on modifications to Shank’s baby-step giant-step method. Their computation model counts basic group operations (group multiplication, inverse, and equality testing) and table lookups. They give complexity results with precise upper bounds in terms of these operations. They also present some implementation results for algorithms for class groups of imaginary quadratic orders. Reviewer: J.Sorenson (Indianapolis) Cited in 4 ReviewsCited in 16 Documents MSC: 11Y16 Number-theoretic algorithms; complexity 20K01 Finite abelian groups Keywords:order computation problems; discrete logarithm problem; algorithm; structure problem; complexity results; class groups of imaginary quadratic orders; computational group theory; baby-step giant-step; finite abelian groups Software:LiDIA PDFBibTeX XMLCite \textit{J. Buchmann} et al., Math. Comput. 66, No. 220, 1663--1687 (1997; Zbl 0894.11050) Full Text: DOI