On some computational problems in finite abelian groups
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.
- Computing in general Abelian groups is hard
- The Pohlig-Hellman method generalized for group structure computation
- Computing discrete logarithms in quadratic orders
- Roots of unity in orders
- A Terr algorithm for computations in the infrastructure of real-quadratic number fields
- Computable abelian groups
- Unconditional class group tabulation of imaginary quadratic fields to \(| \Delta| < 2^{40}\)
- Efficient algorithms for the basis of finite abelian groups
- A generic approach to searching for Jacobians
- Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
- Structure computation and discrete logarithms in finite abelian \(p\)-groups
- scientific article; zbMATH DE number 6004943 (Why is no real title available?)
- scientific article; zbMATH DE number 3871319 (Why is no real title available?)
- A space efficient algorithm for group structure computation
- scientific article; zbMATH DE number 1257081 (Why is no real title available?)
- Determining the small solutions to 𝑆-unit equations
- A modification of Shanks' baby-step giant-step algorithm
- Computing normal integral bases of abelian number fields
- Public-key cryptosystem based on invariants of diagonalizable groups
- Computing the structure of a finite abelian group
- Construction of hyperelliptic function fields of high three-rank
- Quadratic class numbers and character sums
- Linear and sublinear time algorithms for the basis of abelian groups
- Picard Groups and Refined Discrete Logarithms
- Computing the binomial part of a polynomial ideal
- Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes
- Unconditional computation of the class groups of real quadratic fields
- A low-memory algorithm for finding short product representations in finite groups.
- Root extraction in finite abelian groups
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)