Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

On some computational problems
in finite abelian groups


Authors: Johannes Buchmann, Michael J. Jacobson Jr. and Edlyn Teske
Journal: Math. Comp. 66 (1997), 1663-1687
MSC (1991): Primary 11Y16
DOI: https://doi.org/10.1090/S0025-5718-97-00880-6
MathSciNet review: 1432126
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $O$-constants and $\Omega $-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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16

Retrieve articles in all journals with MSC (1991): 11Y16


Additional Information

Johannes Buchmann
Affiliation: Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany
Email: buchmann@cdc.informatik.th-darmstadt.de

Michael J. Jacobson Jr.
Affiliation: Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany
Email: jacobs@cdc.informatik.th-darmstadt.de

Edlyn Teske
Affiliation: Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany
Email: teske@cdc.informatik.th-darmstadt.de

DOI: https://doi.org/10.1090/S0025-5718-97-00880-6
Received by editor(s): April 1, 1996
Received by editor(s) in revised form: July 19, 1996
Additional Notes: The second author was supported by the Natural Sciences and Engineering Research Council of Canada
The third author was supported by the Deutsche Forschungsgemeinschaft
Article copyright: © Copyright 1997 American Mathematical Society