×

A space efficient algorithm for group structure computation. (English) Zbl 0965.11050

Summary: 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.

MSC:

11Y16 Number-theoretic algorithms; complexity
20-04 Software, source code, etc. for problems pertaining to group theory
11R65 Class groups and Picard groups of orders
11R29 Class numbers, class groups, discriminants
11Y40 Algebraic number theory computations
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0894.11050

Software:

LiDIA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0894.11050
[2] Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2, 176 – 184. · Zbl 0439.65001 · doi:10.1007/BF01933190
[3] 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.
[4] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[5] J.-J. Quisquater and J. Vandewalle , Advances in cryptology — EUROCRYPT ’89, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, Berlin, 1990.
[6] 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. · Zbl 0302.68010
[7] 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. · Zbl 0895.68055
[8] LiDIA Group, Universität des Saarlandes, Saarbrücken, Germany. LiDIA - A library for computational number theory, Version 1.2, 1996.
[9] C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289 – 311. · Zbl 0559.10004
[10] H. W. Lenstra Jr. and R. Tijdeman , Computational methods in number theory. Part II, Mathematical Centre Tracts, vol. 155, Mathematisch Centrum, Amsterdam, 1982. · Zbl 0497.00005
[11] 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. · doi:10.1090/psapm/042/1095551
[13] R.J. Schoof. Quadratic fields and factorization. In Lenstra, Jr. and Tijdeman [LT82], pages 235-286. · Zbl 0527.12003
[14] 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.
[15] 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.
[16] J. Sattler and C.-P. Schnorr, Generating random walks in groups, Ann. Univ. Sci. Budapest. Sect. Comput. 6 (1985), 65 – 79 (1987). · Zbl 0655.60009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.