Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

   
 
 

 

Structure computation and discrete logarithms in finite abelian $ p$-groups


Author: Andrew V. Sutherland
Journal: Math. Comp. 80 (2011), 477-500
MSC (2010): Primary 11Y16; Secondary 20K01, 12Y05
DOI: https://doi.org/10.1090/S0025-5718-10-02356-2
Published electronically: April 16, 2010
MathSciNet review: 2728991
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a generic algorithm for computing discrete logarithms in a finite abelian $ p$-group $ H$, improving the Pohlig-Hellman algorithm and its generalization to noncyclic groups by Teske. We then give a direct method to compute a basis for $ H$ without using a relation matrix. The problem of computing a basis for some or all of the Sylow $ p$-subgroups of an arbitrary finite abelian group $ G$ is addressed, yielding a Monte Carlo algorithm to compute the structure of $ G$ using $ O(\vert G\vert^{1/2})$ group operations. These results also improve generic algorithms for extracting $ p$th roots in $ G$.


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

  • 1. Vincenzo Acciaro, The probability of generating some common families of finite groups, Utilitas Mathematica 49 (1996), 243-254. MR 1396305 (97c:20106)
  • 2. Leonard M. Adleman, Kenneth Manders, and Gary L. Miller, On taking roots in finite fields, Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, 1977, pp. 175-178. MR 0502224 (58:19339)
  • 3. László Babai and Robert Beals, A polynomial-time theory of black-box groups. I, Groups St. Andrews 1997 in Bath, I, London Mathematical Society Lecture Notes Series, vol. 260, Cambridge University Press, 1999, pp. 30-64. MR MR1676609 (2000h:20089)
  • 4. Daniel J. Bernstein, Faster square roots in annoying finite fields, http://cr.yp.to /papers/sqroot.pdf, 2001.
  • 5. -, Pippenger's exponentiation algorithm, http://cr.yp.to/papers/pippenger.pdf, 2001.
  • 6. Ernest F. Brickell, Daniel M. Gordon, Kevin S. McCurley, and David B. Wilson, Fast exponentiation with precomputation, Advances in Cryptology-EUROCRYPT '92, Lecture Notes in Computer Science, vol. 658, Springer-Verlag, 1992, pp. 200-207.
  • 7. Johannes Buchmann, Michael J. Jacobson, Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Mathematics of Computation 66 (1997), 1663-1687. MR 1432126 (98a:11185)
  • 8. Johannes Buchmann and Arthur Schmidt, Computing the structure of a finite abelian group, Mathematics of Computation 74 (2005), 2017-2026. MR 2164109 (2006c:20108)
  • 9. Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms: An algorithmic approach, Algorithms and Computations in Mathematics, vol. 20, Springer, 2007. MR 2300780 (2008b:11046)
  • 10. Frank Celler and C. R. Leedham-Green, Calculating the order of an invertible matrix, Groups and Computation II, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, American Mathematical Society, 1997, pp. 55-60. MR 1444130 (98g:20001)
  • 11. Henri Cohen, A course in computational algebraic number theory, Springer, 1996. MR 1228206 (94i:11105)
  • 12. Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), 129-146. MR 1613189 (99g:94014)
  • 13. Donald E. Knuth, The art of computer programming, vol. IV, fascicle 2: Generating all tuples and permutations, Addison-Wesley, 2005. MR 2251595 (2007f:68004b)
  • 14. Chae Hoon Lim and Pil Joong Lee, More flexible exponentiation with precomputation, Advances in Cryptology-CRYPTO '94, Lecture Notes in Computer Science, vol. 839, Springer, 1994, pp. 95-107. MR 1316405 (95k:94020)
  • 15. Kevin S. McCurley, The discrete logarithm problem, Cryptography and Computational Number Theory (C. Pomerance, ed.), Proceedings of Symposia in Applied Mathematics, vol. 42, American Mathematical Society, 1990, p. 4974. MR 1095551 (92d:11133)
  • 16. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press, 1997, revised reprint. MR 1412797 (99g:94015)
  • 17. Andrew Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography 19 (2000), 129-145. MR 1759614
  • 18. Nicholas Pippenger, On the evaluation of powers and related problems (preliminary version), 17th Annual Symposium on Foundations of Computer Science, IEEE, 1976, pp. 258-263. MR 0483702 (58:3682)
  • 19. Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $ {GF}(p)$ and its cryptographic significance, IEEE Transactions on Information Theory 24 (1978), 106-110. MR 0484737 (58:4617)
  • 20. John M. Pollard, Monte Carlo methods for index computations mod $ p$, Mathematics of Computation 32 (1978), 918-924. MR 0491431 (58:10684)
  • 21. Carl Pomerance, The expected number of random elements to generate a finite abelian group, Periodica Mathematica Hungarica 43 (2001), 191-198. MR 1830576 (2002h:20101)
  • 22. Donald Shanks, Class number, a theory of factorization and genera, Analytic Number Theory, Proceedings of Symposia on Pure Mathematics, vol. 20, American Mathematical Society, 1971, pp. 415-440. MR 0316385 (47:4932)
  • 23. -, Five number-theoretic algorithms, Proceedings of the 2nd Manitoba Conference on Numerical Mathematics, 1972, pp. 51-70. MR 0371855 (51:8072)
  • 24. Victor Shoup, Lower bounds for discrete logarithms and related problems, Advances in Cryptology-EUROCRYPT '97, Lecture Notes in Computer Science, vol. 1233, Springer-Verlag, 1997, revised version, pp. 256-266. MR 1603068 (98j:94023)
  • 25. -, A computational introduction to number theory and algebra, Cambridge University Press, 2005. MR 2151586 (2006g:11003)
  • 26. Andrew V. Sutherland, Order computations in generic groups, Ph.D. thesis, MIT, 2007, http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
  • 27. -, Extracting roots in finite abelian groups, 2008, in preparation.
  • 28. Edlyn Teske, A space efficient algorithm for group structure computation, Mathematics of Computation 67 (1998), 1637-1663. MR 1474658 (99a:11146)
  • 29. -, Speeding up Pollard's rho method for computing discrete logarithms, Algorithmic Number Theory Symposium-ANTS III, Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, 1998, pp. 541-554. MR 1726100 (2000j:11199)
  • 30. -, The Pohlig-Hellman method generalized for group structure computation, Journal of Symbolic Computation 27 (1999), 521-534. MR 1701092 (2000f:20090)
  • 31. Alberto Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Göttinger Nachrichten (1891), 344-346.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 20K01, 12Y05

Retrieve articles in all journals with MSC (2010): 11Y16, 20K01, 12Y05


Additional Information

Andrew V. Sutherland
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: drew@math.mit.edu

DOI: https://doi.org/10.1090/S0025-5718-10-02356-2
Received by editor(s): September 19, 2008
Received by editor(s) in revised form: July 27, 2009, and August 29, 2009
Published electronically: April 16, 2010
Article copyright: © Copyright 2010 by the author

American Mathematical Society