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 Free Access
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)$.
- Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI https://doi.org/10.1016/S0747-7171%2808%2980013-2
- P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50–59. MR 882842, DOI https://doi.org/10.1287/moor.12.1.50 K. F. Gauss,Disquisitiones arithmeticæ, Fleischer, Lepzig, 1801. Translation into English by Arthur A. Clarke, S. J., reprinted by Springer-Verlag, New York, 1985.
- Dorian Goldfeld, Gauss’s class number problem for imaginary quadratic fields, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 1, 23–37. MR 788386, DOI https://doi.org/10.1090/S0273-0979-1985-15352-2
- T. C. Hu and R. D. Young, Integer programming and network flows, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0263420
- Loo Keng Hua, Introduction to number theory, Springer-Verlag, Berlin-New York, 1982. Translated from the Chinese by Peter Shiu. MR 665428
- Ravindran Kannan and Achim Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), no. 4, 499–507. MR 573842, DOI https://doi.org/10.1137/0208040
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878 A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Technical Report 87-008, Dep. of Computer Science, Univ. of Chicago, 1987.
- H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
- Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
- Władysław Narkiewicz, Classical problems in number theory, Monografie Matematyczne [Mathematical Monographs], vol. 62, Państwowe Wydawnictwo Naukowe (PWN), Warsaw, 1986. MR 961960
- Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI https://doi.org/10.1007/bf02242355 A. Schönhage, Schnelle Berechnung von Kettenbruchenentwicklungen, Acta Inform. 1 (1971), 139-144.
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI https://doi.org/10.1090/S0025-5718-1987-0878705-X
- 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
- Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
- Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI https://doi.org/10.1109/TIT.1986.1057137
Retrieve articles in Journal of the American Mathematical Society with MSC: 11Y40, 11R29
Retrieve articles in all journals with MSC: 11Y40, 11R29
Additional Information
Article copyright:
© Copyright 1989
American Mathematical Society