Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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

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.


References [Enhancements On Off] (What's this?)

  • [BJT97] J. Buchmann, M.J. Jacobson Jr., and E. Teske. On some computational problems in finite abelian groups. Mathematics of Computation, 66:1663-1687, 1997. MR 98a:11185
  • [Bre80] R.P. Brent. An improved Monte Carlo factorization algorithm. BIT, 20:176-184, 1980. MR 82a:10007
  • [CL83] 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. MR 85g:10007
  • [Coh93] H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993. MR 94i:11105
  • [FO90] P. Flajolet and A.M. Odlyzko. Random mapping statistics. In Advances in Cryptology - EUROCRYPT '89, Lecture Notes in Computer Sci., volume 434, pages 329-354, Springer-Verlag, New York, 1990. MR 91h:94003
  • [Knu73] D.E. Knuth. The art of computer programming. Volume 3: Sorting and searching. Addison-Wesley, Reading, Massachusetts, 1973. MR 56:4281
  • [Knu75] D.E. Knuth. The art of computer programming. Volume 1: Fundamental algorithms. Addison-Wesley, Reading, Massachusetts, 1975. MR 51:14624
  • [LiD96] LiDIA Group, Universität des Saarlandes, Saarbrücken, Germany. LiDIA - A library for computational number theory, Version 1.2, 1996.
  • [LS84] H.W. Lenstra, Jr. and C.P. Schnorr. A Monte Carlo factoring algorithm with linear storage. Mathematics of Computation, 43(167):289-311, 1984. MR 85d:11106
  • [LT82] H.W. Lenstra, Jr. and R. Tijdeman, editors. Computational methods in number theory, volume 154/155 of Mathematical Centre Tracts. Mathematisch Centrum, Amsterdam, 1982. MR 84d:10004
  • [McC90] K. McCurley. The discrete logarithm problem. In Cryptology and Computational Number Theory, Proc. Symp. Appl. Math., vol. 42, pages 49-74. American Mathematic Society, 1990. MR 92d:11133
  • [Pol78] J.M. Pollard. Monte Carlo methods for index computation (mod $p$). Mathematics of Computation, 32(143):918-924, 1978. MR 58:10684
  • [Sch82] R.J. Schoof. Quadratic fields and factorization. In Lenstra, Jr. and Tijdeman [LT82], pages 235-286. MR 85g:11118
  • [Sha71] D. Shanks. Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415-440. AMS, Providence, R.I., 1971. MR 47:4932
  • [Sho96] 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.
  • [SS85] J. Sattler and C.P. Schnorr. Generating random walks in groups. Ann.-Univ.-Sci.-Budapest.-Sect.-Comput., 6:65-79, 1985. MR 89a:68108

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

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

DOI: https://doi.org/10.1090/S0025-5718-98-00968-5
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

American Mathematical Society