Computations of class numbers of real quadratic fields
HTML articles powered by AMS MathViewer
- by Anitha Srinivasan PDF
- Math. Comp. 67 (1998), 1285-1308 Request permission
Abstract:
In this paper an unconditional probabilistic algorithm to compute the class number of a real quadratic field $\mathbb {Q}(\sqrt {d})$ is presented, which computes the class number in expected time $O(d^{1/5+\epsilon })$. The algorithm is a random version of Shanks’ algorithm. One of the main steps in algorithms to compute the class number is the approximation of $L(1, \chi )$. Previous algorithms with the above running time $O(d^{1/5+\epsilon })$, obtain an approximation for $L(1, \chi )$ by assuming an appropriate extension of the Riemann Hypothesis. Our algorithm finds an appoximation for $L(1, \chi )$ without assuming the Riemann Hypothesis, by using a new technique that we call the ‘Random Summation Technique’. As a result, we are able to compute the regulator deterministically in expected time $O(d^{1/5+\epsilon })$. However, our estimate of $O(d^{1/5+\epsilon })$ on the running time of our algorithm to compute the class number is not effective.References
- Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944
- Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
- Harvey Cohn, Advanced number theory, Dover Books on Advanced Mathematics, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962. MR 594936
- Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931, DOI 10.1007/978-1-4757-5927-3
- Duane W. DeTemple, A quicker convergence to Euler’s constant, Amer. Math. Monthly 100 (1993), no. 5, 468–470. MR 1215533, DOI 10.2307/2324300
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- Loo Keng Hua, Introduction to number theory, Springer-Verlag, Berlin-New York, 1982. Translated from the Chinese by Peter Shiu. MR 665428, DOI 10.1007/978-3-642-68130-1
- 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
- H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0
- R. A. Mollin and H. C. Williams, Computation of the class number of a real quadratic field, Utilitas Math. 41 (1992), 259–308. MR 1162532
- Lothar Sachs, Applied statistics, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 1984. Translated from the fifth German edition by Zenon Reynarowych. MR 764398, DOI 10.1007/978-1-4612-5246-7
- 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
- Jeffrey Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Comput. 10 (1990), no. 6, 593–610. MR 1087981, DOI 10.1016/S0747-7171(08)80160-5
- 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, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
Additional Information
- Anitha Srinivasan
- Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
- Address at time of publication: Department of Mathematics, University of Puerto Rico, CUH Station, 100 Carretera 908, Humacao, Puerto Rico 00791-4300
- Email: as@turing.upr.clu.edu
- Received by editor(s): July 2, 1996
- Received by editor(s) in revised form: January 31, 1997
- © Copyright 1998 American Mathematical Society
- Journal: Math. Comp. 67 (1998), 1285-1308
- MSC (1991): Primary 11A51
- DOI: https://doi.org/10.1090/S0025-5718-98-00965-X
- MathSciNet review: 1468944