On some computational problems in finite abelian groups

Johannes Buchmann, Michael J. Jacobson, Edlyn Teske

Mathematics of Computation · 1997 · 52 citations · 2 references

DOIFull text

Open access

Concepts

Abstract

We present new algorithms for computing orders of elements, discrete logarithms, and structures of finite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly determine the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O"> <mml:semantics> <mml:mi>O</mml:mi> <mml:annotation encoding="application/x-tex">O</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -constants and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Omega"> <mml:semantics> <mml:mi mathvariant="normal"> Ω </mml:mi> <mml:annotation encoding="application/x-tex">\Omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our experimental results. Our algorithms are based on a modification of Shanks’ baby-step giant-step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order.

References

2