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.8635047078132629
0 references
0.8576955795288086
0 references
0.8575979471206665
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