A space efficient algorithm for group structure computation

Author:
Edlyn Teske

Journal:
Math. Comp. **67** (1998), 1637-1663

MSC (1991):
Primary 11Y16

DOI:
https://doi.org/10.1090/S0025-5718-98-00968-5

MathSciNet review:
1474658

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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 https://doi.org/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 https://doi.org/10.1007/BF01933190 - H. Cohen and H.W. Lenstra, Jr. Heuristics on class groups of number fields. In
*Number Theory*, Lecture notes in Math., volume 1068, pages 33–62. Springer-Verlag, New York, 1984. - Henri Cohen,
*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206** - 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 Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR**0445948** - Donald E. Knuth,
*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. 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 https://doi.org/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 https://doi.org/10.1090/psapm/042/1095551 - J. M. Pollard,
*Monte Carlo methods for index computation $({\rm mod}\ p)$*, Math. Comp.**32**(1978), no. 143, 918–924. MR**491431**, DOI https://doi.org/10.1090/S0025-5718-1978-0491431-9 - R.J. Schoof. Quadratic fields and factorization. In Lenstra, Jr. and Tijdeman [
*Computational methods in number theory*, volume 154/155 of*Mathematical Centre Tracts*. Mathematisch Centrum, Amsterdam, 1982.], pages 235–286. - 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**

Retrieve articles in *Mathematics of Computation*
with MSC (1991):
11Y16

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

Additional Information

**Edlyn Teske**

Affiliation:
Technische Universität Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10 64283 Darmstadt Germany

Address at time of publication:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Email:
teske@cdc.informatik.tu-darmstadt.de

Keywords:
Generic algorithms; group structure computation; Pollard’s $\rho$-method; class groups

Received by editor(s):
February 7, 1997

Received by editor(s) in revised form:
April 23, 1997

Article copyright:
© Copyright 1998
American Mathematical Society