A space efficient algorithm for group structure computation

Teske, Edlyn

doi:10.1090/S0025-5718-98-00968-5

A space efficient algorithm for group structure computation
HTML articles powered by AMS MathViewer

by Edlyn Teske PDF

Math. Comp. 67 (1998), 1637-1663 Request permission

Abstract:

We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is $O(\sqrt {n})$ (with $n$ denoting the group order), and we explicitly determine the $O$-constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.

References

Johannes Buchmann, Michael J. Jacobson Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Math. Comp. 66 (1997), no. 220, 1663–1687. MR 1432126, DOI 10.1090/S0025-5718-97-00880-6
Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2, 176–184. MR 583032, DOI 10.1007/BF01933190
Alfred Rosenblatt, Sur les points singuliers des équations différentielles, C. R. Acad. Sci. Paris 209 (1939), 10–11 (French). MR 85
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
J.-J. Quisquater and J. Vandewalle (eds.), Advances in cryptology—EUROCRYPT ’89, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, Berlin, 1990. MR 1083956
Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
LiDIA Group, Universität des Saarlandes, Saarbrücken, Germany. LiDIA - A library for computational number theory, Version 1.2, 1996.
C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, DOI 10.1090/S0025-5718-1984-0744939-5
H. W. Lenstra Jr. and R. Tijdeman (eds.), Computational methods in number theory. Part II, Mathematical Centre Tracts, vol. 155, Mathematisch Centrum, Amsterdam, 1982. MR 702516
Kevin S. McCurley, The discrete logarithm problem, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49–74. MR 1095551, DOI 10.1090/psapm/042/1095551
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
Alfred Rosenblatt, Sur les points singuliers des équations différentielles, C. R. Acad. Sci. Paris 209 (1939), 10–11 (French). MR 85
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
V. Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology–Eurocrypt ’97, Lectures Notes in Computer Sci., Volume 1233, pp. 256–266, Springer-Verlag, New York, 1997.
J. Sattler and C.-P. Schnorr, Generating random walks in groups, Ann. Univ. Sci. Budapest. Sect. Comput. 6 (1985), 65–79 (1987). MR 915225