Computations of class numbers

of real quadratic fields

Author:
Anitha Srinivasan

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

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 is presented, which computes the class number in expected time . 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 . Previous algorithms with the above running time , obtain an approximation for by assuming an appropriate extension of the Riemann Hypothesis. Our algorithm finds an appoximation for 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 . However, our estimate of on the running time of our algorithm to compute the class number is not effective.

**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**

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

Email:
as@turing.upr.clu.edu

DOI:
https://doi.org/10.1090/S0025-5718-98-00965-X

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