On some computational problems in finite abelian groups (Q4372641)

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 1097172
Language Label Description Also known as
default for all languages
No label defined
    English
    On some computational problems in finite abelian groups
    scientific article; zbMATH DE number 1097172

      Statements

      On some computational problems in finite abelian groups (English)
      0 references
      16 December 1997
      0 references
      order computation problems
      0 references
      discrete logarithm problem
      0 references
      algorithm
      0 references
      structure problem
      0 references
      complexity results
      0 references
      class groups of imaginary quadratic orders
      0 references
      computational group theory
      0 references
      baby-step giant-step
      0 references
      finite abelian groups
      0 references
      0 references
      0 references
      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.
      0 references

      Identifiers