A rigorous subexponential algorithm for computation of class groups
HTML articles powered by AMS MathViewer
- by James L. Hafner and Kevin S. McCurley
- J. Amer. Math. Soc. 2 (1989), 837-850
- DOI: https://doi.org/10.1090/S0894-0347-1989-1002631-0
- PDF | Request permission
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
- Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-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 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 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 10.1137/0208040
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. 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 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 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) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. 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 10.1109/TIT.1986.1057137
Bibliographic Information
- © Copyright 1989 American Mathematical Society
- 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