Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Computations of class numbers
of real quadratic fields

Author: Anitha Srinivasan
Journal: Math. Comp. 67 (1998), 1285-1308
MSC (1991): Primary 11A51
MathSciNet review: 1468944
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. R. P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, J. Assoc. Comp. Mach. 23 (1976), 242- 251.MR 52:16111
  • 2. D. Buell, Binary Quadratic Forms, Springer-Verlag, New York/Berlin/Heidelberg, 1989. MR 92b:11021
  • 3. H. Cohn, Advanced Number Theory, Dover, Inc. New York, 1980. MR 82b:12001
  • 4. H. Davenport, Multiplicative Number Theory (4th, ed.), Springer-Verlag, New York, 1980, 111-222. MR 82m:10001
  • 5. D. W. DeTemple, A quicker Convergence to Euler's Constant, Amer. Math. Monthly 100 (1993), 468-470. MR 94e:11146
  • 6. G. H. Hardy and E.M. Wright, An introduction to the theory of numbers, 5th ed, Oxford Science Publication. MR 81i:10002
  • 7. L. K. Hua, Introduction to Number Theory, Springer-Verlag, New York, 1982. MR 83f:10001
  • 8. H. W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, Lond. Math. Soc. Lect. Note Ser, 56 (1982), 123-150. MR 86g:11080
  • 9. H. W. Lenstra, Jr. and C. Pomerance, A rigorous time bound for factoring integers, Journal of the Americain Mathematical Society 5, (1992). MR 92m:11145
  • 10. R. A. Mollin and H. Williams, Computation of the class number of real quadratic fields, Utilitas Math., 41 (1992), 259-308. MR 93d:11134
  • 11. L. Sachs, Applied Statistics, A handbook of techniques, 2nd ed., pp 64, Springer-Verlag, New York/Berlin/Heidelberg/Tokyo, 1984. MR 85k:62001
  • 12. R. J. Schoof, Quadratic fields and factorization, Computational methods in number theory, (H. W. Lenstra, Jr., and R.Tijdeman, eds.), Math.Centrum, Number 155, part II, Amsterdam 1 (1983), 235-286. MR 85g:11118b
  • 13. J.Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Computation 10 (1990), 593-610. MR 91m:11112
  • 14. D.Shanks, Class number, a theory of factorization, and genera, Proc. Symp. Pure Math., Amer. Math. Soc. 20 (1971), 415-440. MR 47:4932
  • 15. D.Shanks, The infrastructure of real quadratic fields and its application, Proc.1972 Number Theory Conf.,Boulder, Colorado (1973), 217-224. MR 52:10672
  • 16. T. Tatuzawa, On a theorem of Siegel, Japan J. Math. 21 (1951), 163-178. MR 14:452c

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A51

Retrieve articles in all journals with MSC (1991): 11A51

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

Keywords: Class number, binary quadratic forms, real quadratic field, regulator
Received by editor(s): July 2, 1996
Received by editor(s) in revised form: January 31, 1997
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society