Computations of class numbers of real quadratic fields
Author:
Anitha Srinivasan
Journal:
Math. Comp. 67 (1998), 12851308
MSC (1991):
Primary 11A51
MathSciNet review:
1468944
Fulltext PDF Free Access
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.
Richard
P. Brent, Fast multipleprecision evaluation of elementary
functions, J. Assoc. Comput. Mach. 23 (1976),
no. 2, 242–251. MR 0395314
(52 #16111)
 2.
Duncan
A. Buell, Binary quadratic forms, SpringerVerlag, New York,
1989. Classical theory and modern computations. MR 1012948
(92b:11021)
 3.
Harvey
Cohn, Advanced number theory, Dover Publications, Inc., New
York, 1980. Reprint of A second course in number theory, 1962; Dover Books
on Advanced Mathematics. MR 594936
(82b:12001)
 4.
Harold
Davenport, Multiplicative number theory, 2nd ed., Graduate
Texts in Mathematics, vol. 74, SpringerVerlag, New YorkBerlin, 1980.
Revised by Hugh L. Montgomery. MR 606931
(82m:10001)
 5.
Duane
W. DeTemple, A quicker convergence to Euler’s constant,
Amer. Math. Monthly 100 (1993), no. 5, 468–470.
MR
1215533 (94e:11146), http://dx.doi.org/10.2307/2324300
 6.
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
(81i:10002)
 7.
Loo
Keng Hua, Introduction to number theory, SpringerVerlag,
BerlinNew York, 1982. Translated from the Chinese by Peter Shiu. MR 665428
(83f:10001)
 8.
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
(86g:11080)
 9.
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
(92m:11145), http://dx.doi.org/10.1090/S08940347199211371000
 10.
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
(93d:11134)
 11.
Lothar
Sachs, Applied statistics, 2nd ed., Springer Series in
Statistics, SpringerVerlag, New York, 1984. Translated from the fifth
German edition by Zenon Reynarowych. MR 764398
(85k:62001)
 12.
R.
J. Schoof, Quadratic fields and factorization, Computational
methods in number theory, Part II, Math. Centre Tracts, vol. 155,
Math. Centrum, Amsterdam, 1982, pp. 235–286. MR 702519
(85g:11118b)
 13.
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
(91m:11112), http://dx.doi.org/10.1016/S07477171(08)801605
 14.
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
(47 #4932)
 15.
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
(52 #10672)
 16.
Tikao
Tatuzawa, On a theorem of Siegel, Jap. J. Math.
21 (1951), 163–178 (1952). MR 0051262
(14,452c)
 1.
 R. P. Brent, Fast MultiplePrecision Evaluation of Elementary Functions, J. Assoc. Comp. Mach. 23 (1976), 242 251.MR 52:16111
 2.
 D. Buell, Binary Quadratic Forms, SpringerVerlag, 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.), SpringerVerlag, New York, 1980, 111222. MR 82m:10001
 5.
 D. W. DeTemple, A quicker Convergence to Euler's Constant, Amer. Math. Monthly 100 (1993), 468470. 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, SpringerVerlag, 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), 123150. 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), 259308. MR 93d:11134
 11.
 L. Sachs, Applied Statistics, A handbook of techniques, 2nd ed., pp 64, SpringerVerlag, 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), 235286. MR 85g:11118b
 13.
 J.Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Computation 10 (1990), 593610. MR 91m:11112
 14.
 D.Shanks, Class number, a theory of factorization, and genera, Proc. Symp. Pure Math., Amer. Math. Soc. 20 (1971), 415440. MR 47:4932
 15.
 D.Shanks, The infrastructure of real quadratic fields and its application, Proc.1972 Number Theory Conf.,Boulder, Colorado (1973), 217224. MR 52:10672
 16.
 T. Tatuzawa, On a theorem of Siegel, Japan J. Math. 21 (1951), 163178. 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 007914300
Email:
as@turing.upr.clu.edu
DOI:
http://dx.doi.org/10.1090/S002557189800965X
PII:
S 00255718(98)00965X
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
