Mathematics of Computation · 1997 · 52 citations · 2 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationAbstract AlgebraComputational ComplexityComputational Number TheoryGroup TheoryNumber-theoretic AlgorithmsStructural ComplexityAnnotation EncodingComputational Group TheoryDiscrete Logarithm AlgorithmsDiscrete Logarithm ProblemFinite Abelian Groups
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.
2
Residual hermite normal form computations
Paul D. Domich · ACM Transactions on Mathematical Software · 1989 · 10 citations · Full text