On some computational problems in finite abelian groups

From MaRDI portal





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.




Cited in
(29)


Describes a project that uses

Uses Software






This page was built for publication: On some computational problems in finite abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4372641)