On some computational problems in finite abelian groups

Buchmann, Johannes; Jacobson, Michael, Jr.; Teske, Edlyn

doi:10.1090/S0025-5718-97-00880-6

On some computational problems in finite abelian groups
HTML articles powered by AMS MathViewer

by Johannes Buchmann, Michael J. Jacobson Jr. and Edlyn Teske PDF

Math. Comp. 66 (1997), 1663-1687 Request permission

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

Ingrid Biehl and Johannes Buchmann, Algorithms for quadratic orders, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 425–449. MR 1314882, DOI 10.1090/psapm/048/1314882
J. Buchmann and S. Paulus, Algorithms for finite abelian groups, Extended abstract. To be published in the proceedings of NTAMCS 93.
Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62. MR 756082, DOI 10.1007/BFb0099440
Paul D. Domich, Residual Hermite normal form computations, ACM Trans. Math. Software 15 (1989), no. 3, 275–286. MR 1062493, DOI 10.1145/66888.66892
J. Buchmann I. Biehl and T. Papanikolaou, LiDIA - a library for computational number theory, The LiDIA Group, Universität des Saarlandes, Saarbrücken, Germany, 1995.
A.K. Lenstra and H.W. Lenstra, Jr., Algorithms in number theory, Handbook of theoretical computer science (J. van Leeuwen, ed.), Elsevier Science Publishers, 1990, pp. 673–715.
S. Paulus, Algorithmen für endliche abelsche Gruppen, Master’s thesis, Universität des Saarlandes, Saarbrücken, Germany, 1992.
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385