Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

A rigorous subexponential algorithm for computation of class groups


Authors: James L. Hafner and Kevin S. McCurley
Journal: J. Amer. Math. Soc. 2 (1989), 837-850
MSC: Primary 11Y40; Secondary 11R29
DOI: https://doi.org/10.1090/S0894-0347-1989-1002631-0
MathSciNet review: 1002631
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ C( - d)$ denote the Gauss Class Group of quadratic forms of a negative discriminant $ - d$ (or equivalently, the class group of the imaginary quadratic field $ Q(\sqrt { - d} )$). We give a rigorous proof that there exists a Las Vegas algorithm that will compute the structure of $ C( - d)$ with an expected running time of $ L{(d)^{\sqrt 2 + o(1)}}$ bit operations, where $ L(d) = {\text{exp}}(\sqrt {\log \,d\;\log \,\log \,d} )$. Thus, of course, also includes the computation of the class number $ h( - d)$, the cardinality of $ C( - d)$.


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

  • [1] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, preprint, 1987. Extended abstract in Proc. 19th ACM Sympos. on Theory of Comput. ACM, New York, 1987, pp. 1-6. MR 1056627 (91i:68058)
  • [2] P. D. Domich, R. Kannan, and L. E. Trotter, Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), 50-59. MR 882842 (88e:65047)
  • [3] K. F. Gauss,Disquisitiones arithmeticæ, Fleischer, Lepzig, 1801. Translation into English by Arthur A. Clarke, S. J., reprinted by Springer-Verlag, New York, 1985.
  • [4] D. Goldfeld, Gauss' class number problem for imaginary quadratic fields, Bull. Amer. Math. Soc. 13 (1985), 23-37. MR 788386 (86k:11065)
  • [5] T. C. Hu, Integer programming and network flows, Addison-Wesley, Reading, MA, 1969. MR 0263420 (41:8025)
  • [6] Hua Loo Keng, Introduction to number theory. Translation into English by Peter Shiu, Springer-Verlag, New York, 1982. MR 665428 (83f:10001)
  • [7] Ravindran Kannan and Achim Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), 499-507. MR 573842 (81k:15002)
  • [8] D. E. Knuth, The art of computer programming, Vol. 2: Seminumerical algorithms, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 633878 (83i:68003)
  • [9] A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Technical Report 87-008, Dep. of Computer Science, Univ. of Chicago, 1987.
  • [10] H. W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, Journées Arithmétiques 1980 (J. V. Armitage, ed.), Cambridge Univ. Press, New York, 1982. MR 697260 (86g:11080)
  • [11] Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number Theory and Applications (Proc. NATO Advanced Study Inst. on Number Theory and Applications, Banff, 1988) (Richard A. Molin, ed.), Kluwer, Boston, 1989. MR 1123090 (92e:11149)
  • [12] W. Narkiewicz, Classical problems in number theory, PWN, Polish Sci. Publ., Warsaw, 1986. MR 961960 (90e:11002)
  • [13] Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity (Proc. Japan-US Joint Seminar, June 1986, Kyoto, Japan), Academic Press, Orlando, 1987, pp. 119-143. MR 910929 (88m:11109)
  • [14] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • [15] A. Schönhage, Schnelle Berechnung von Kettenbruchenentwicklungen, Acta Inform. 1 (1971), 139-144.
  • [16] R. Schoof, Quadratic fields and factorization, Computation Methods in Number Theory (R. Tijdeman and H. W. Lenstra, Jr., eds.), Math. Centrum Tract 154, Amsterdam, 1982, pp. 235-286. MR 702519 (85g:11118b)
  • [17] A. Schrijver, Theory of linear and integer programming, Wiley, New York, 1985. MR 874114 (88m:90090)
  • [18] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), 757-780. MR 878705 (88d:11129)
  • [19] Daniel Shanks, Class number, a theory of factorization, and genera, Proc. Sympos. Pure Math., Vol. 20, Amer. Math. Soc., Providence, RI, 1971, pp. 415-440. MR 0316385 (47:4932)
  • [20] -, Five number-theoretic algorithms, Proc. Second Manitoba Conference on Numerical Mathematics, Univ. of Manitoba, Congressus Numerantium, No. VII, Utilitas. Math., Winnipeg, 1973, pp. 51-70. MR 0371855 (51:8072)
  • [21] Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62. MR 831560 (87g:11166)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 11Y40, 11R29

Retrieve articles in all journals with MSC: 11Y40, 11R29


Additional Information

DOI: https://doi.org/10.1090/S0894-0347-1989-1002631-0
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society