{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:50:04Z","timestamp":1776844204854,"version":"3.51.2"},"reference-count":34,"publisher":"American Mathematical Society (AMS)","issue":"255","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present an algorithm for computing the class number of the quadratic number field of discriminant\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The algorithm terminates unconditionally with the correct answer and, under the GRH, executes in\n \n \n \n \n \n O<\/mml:mi>\n \n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n (<\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n \n \n |<\/mml:mo>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 4<\/mml:mn>\n +<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O_{\\varepsilon }(|d|^{1\/4+\\varepsilon })<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n steps. The technique used combines algebraic methods with Burgess\u2019 theorem on character sums to estimate\n \n \n \n \n L<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \n \n \u03c7\n \n <\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n L(1,\\chi _d)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We give an explicit version of Burgess\u2019 theorem valid for prime discriminants and, as an application, we compute the class number of a 32-digit discriminant.\n <\/p>","DOI":"10.1090\/s0025-5718-06-01850-3","type":"journal-article","created":{"date-parts":[[2006,5,24]],"date-time":"2006-05-24T14:43:01Z","timestamp":1148481781000},"page":"1481-1492","source":"Crossref","is-referenced-by-count":17,"title":["Quadratic class numbers and character sums"],"prefix":"10.1090","volume":"75","author":[{"given":"Andrew","family":"Booker","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2006,3,21]]},"reference":[{"issue":"246","key":"1","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1090\/S0025-5718-03-01501-1","article-title":"Prime sieves using binary quadratic forms","volume":"73","author":"Atkin, A. O. L.","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1090\/psapm\/048\/1314882","article-title":"Algorithms for quadratic orders","author":"Biehl, Ingrid","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821802917"},{"key":"3","unstructured":"Andrew R. Booker and Andreas Str\u00f6mbergsson. Numerical computations with the trace formula and the Selberg eigenvalue conjecture, Crelle (to appear)."},{"key":"4","unstructured":"J. Buchmann. Algorithms for Binary Quadratic Forms. Springer-Verlag, to appear."},{"key":"5","isbn-type":"print","first-page":"53","article-title":"A probabilistic class group and regulator algorithm and its implementation","author":"Buchmann, J.","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/3110123940"},{"key":"6","isbn-type":"print","first-page":"27","article-title":"A subexponential algorithm for the determination of class groups and regulators of algebraic number fields","author":"Buchmann, Johannes","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0817634932"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-322-95233-2_5","article-title":"Distributed class group computation","author":"Buchmann, Johannes","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3815420334"},{"key":"8","isbn-type":"print","first-page":"3","article-title":"Sieving methods for class group computation","author":"Buchmann, Johannes","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646701"},{"issue":"220","key":"9","doi-asserted-by":"publisher","first-page":"1663","DOI":"10.1090\/S0025-5718-97-00880-6","article-title":"On some computational problems in finite abelian groups","volume":"66","author":"Buchmann, Johannes","year":"1997","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1112\/S0025579300001157","article-title":"The distribution of quadratic residues and non-residues","volume":"4","author":"Burgess, D. A.","year":"1957","journal-title":"Mathematika","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5793","issn-type":"print"},{"key":"11","isbn-type":"print","first-page":"35","article-title":"Calculs de nombres de classes et de r\u00e9gulateurs de corps quadratiques en temps sous-exponentiel","author":"Cohen, H.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0817636846"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BFb0099440","article-title":"Heuristics on class groups of number fields","author":"Cohen, H.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/3540133569"},{"key":"13","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"14","unstructured":"R. De Haan, M. J. Jacobson, Jr., and H. C. Williams. A fast, rigorous technique for verifying the regulator of a real quadratic field. preprint, 2004."},{"key":"15","unstructured":"P. Dusart. Autour de la fonction qui compte le nombre de nombres premiers. Universit\u00e9 de Limoges, Ph.D. thesis, 1998."},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.2307\/2374229","article-title":"On Burgess\u2019 bound for primitive roots modulo primes and an application to \u0393(\ud835\udc5d)","volume":"103","author":"Grosswald, E.","year":"1981","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"837","DOI":"10.2307\/1990896","article-title":"A rigorous subexponential algorithm for computation of class groups","volume":"2","author":"Hafner, James L.","year":"1989","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"18","unstructured":"H. A. Helfgott and A. Venkatesh. Integral points on elliptic curves and 3-torsion in class groups. preprint, 2004."},{"key":"19","series-title":"American Mathematical Society Colloquium Publications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/053","volume-title":"Analytic number theory","volume":"53","author":"Iwaniec, Henryk","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821836331"},{"key":"20","isbn-type":"print","first-page":"89","article-title":"The efficiency and security of a real quadratic field based key exchange protocol","author":"Jacobson, Michael J., Jr.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3110170469"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"405","DOI":"10.4064\/aa111-4-2","article-title":"Lower bound of real primitive \ud835\udc3f-function at \ud835\udc60=1","volume":"111","author":"Ji, Chun-Gang","year":"2004","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"22","unstructured":"A. K. Lenstra and H. W. Lenstra, Jr. Algorithms in number theory. Tech. Report 97-008, 1987."},{"key":"23","isbn-type":"print","first-page":"673","article-title":"Algorithms in number theory","author":"Lenstra, A. K.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"24","isbn-type":"print","first-page":"123","article-title":"On the calculation of regulators and class numbers of quadratic fields","author":"Lenstra, H. W., Jr.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0521285135"},{"key":"25","doi-asserted-by":"crossref","unstructured":"J.E. Littlewood. On the class number of the corpus \ud835\udc5d(\u221a-\ud835\udc58). Proc. London Math. Soc., 27:358\u2013372, 1928.","DOI":"10.1112\/plms\/s2-27.1.358"},{"issue":"240","key":"26","doi-asserted-by":"publisher","first-page":"1735","DOI":"10.1090\/S0025-5718-01-01367-9","article-title":"Computation of class numbers of quadratic number fields","volume":"71","author":"Louboutin, St\u00e9phane","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"27","isbn-type":"print","first-page":"459","article-title":"Cryptographic key distribution and computation in class groups","author":"McCurley, Kevin S.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0792301498"},{"key":"28","doi-asserted-by":"crossref","unstructured":"L. B. Pierce. The 3-part of class numbers of quadratic fields. Oxford University, MSc. thesis, 2004.","DOI":"10.1112\/S002461070500637X"},{"key":"29","first-page":"64","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Rosser, J. Barkley","year":"1962","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"key":"30","first-page":"415","article-title":"Class number, a theory of factorization, and genera","author":"Shanks, Daniel","year":"1971"},{"key":"31","first-page":"217","article-title":"The infrastructure of a real quadratic field and its applications","author":"Shanks, Daniel","year":"1972"},{"issue":"223","key":"32","doi-asserted-by":"publisher","first-page":"1285","DOI":"10.1090\/S0025-5718-98-00965-X","article-title":"Computations of class numbers of real quadratic fields","volume":"67","author":"Srinivasan, Anitha","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"33","unstructured":"The PARI Group, Bordeaux. PARI\/GP tutorial, 2004. available from \\url{http:\/\/pari.math.u-bordeaux.fr\/doc.html}."},{"key":"34","unstructured":"The PARI Group, Bordeaux. PARI\/GP, version 2.1.5, 2004. available from \\url{http:\/\/pari.math.u-bordeaux.fr\/}."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-255\/S0025-5718-06-01850-3\/S0025-5718-06-01850-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-255\/S0025-5718-06-01850-3\/S0025-5718-06-01850-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:36:46Z","timestamp":1776782206000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-255\/S0025-5718-06-01850-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3,21]]},"references-count":34,"journal-issue":{"issue":"255","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["S0025-5718-06-01850-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01850-3","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2006,3,21]]}}}