{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:52:42Z","timestamp":1776786762296,"version":"3.51.2"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"260","license":[{"start":{"date-parts":[[2008,4,19]],"date-time":"2008-04-19T00:00:00Z","timestamp":1208563200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present a new algorithm for computing the regulator of a real quadratic field\n \n \n \n \n \n Q<\/mml:mi>\n <\/mml:mrow>\n (<\/mml:mo>\n \n D<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n ,<\/mml:mo>\n <\/mml:mrow>\n \\mathbb {Q}(\\sqrt {D}),<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n based on an algorithm for unconditionally verifying the correctness of the regulator produced by a subexponential algorithm, that runs in expected time\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n D<\/mml:mi>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 6<\/mml:mn>\n +<\/mml:mo>\n \n \u03f5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(D^{1\/6 + \\epsilon })<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n under the Generalized Riemann Hypothesis. The correctness of our algorithm relies on no unproven hypotheses and is currently the fastest known unconditional algorithm for computing the regulator. A number of implementation issues and performance enhancements are discussed, and we present the results of computations demonstrating the efficiency of the new algorithm.\n <\/p>","DOI":"10.1090\/s0025-5718-07-01935-7","type":"journal-article","created":{"date-parts":[[2007,7,26]],"date-time":"2007-07-26T07:46:03Z","timestamp":1185435963000},"page":"2139-2160","source":"Crossref","is-referenced-by-count":4,"title":["A fast, rigorous technique for computing the regulator of a real quadratic field"],"prefix":"10.1090","volume":"76","author":[{"given":"R.","family":"de Haan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"M.","family":"Jacobson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2007,4,19]]},"reference":[{"key":"1","unstructured":"C.S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl and des Regulators reellquadratischer Ordnungen, Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1994."},{"key":"2","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":"3","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"},{"issue":"3-4","key":"4","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1006\/jsco.1996.0143","article-title":"Subexponential algorithms for class group and unit computations","volume":"24","author":"Cohen, H.","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"5","unstructured":"R. de Haan, A fast, rigorous technique for verifying the regulator of a real quadratic field, Master\u2019s thesis, Universiteit van Amsterdam, Amsterdam, May 2004."},{"key":"6","unstructured":"The LiDIA Group, LiDIA: a C++ library for computational number theory, Software, Technische Universit\u00e4t Darmstadt, Germany, 1997. See http:\/\/www.informatik.tu-darmstadt.de\/TI\/LiDIA."},{"issue":"4","key":"7","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"},{"issue":"3","key":"8","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1080\/10586458.1995.10504322","article-title":"An investigation of bounds for the regulator of quadratic fields","volume":"4","author":"Jacobson, Michael J., Jr.","year":"1995","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"issue":"244","key":"9","doi-asserted-by":"publisher","first-page":"2099","DOI":"10.1090\/S0025-5718-03-01465-0","article-title":"A computational approach for solving \ud835\udc66\u00b2=1^{\ud835\udc58}+2^{\ud835\udc58}+\u2026+\ud835\udc65^{\ud835\udc58}","volume":"72","author":"Jacobson, M. J., Jr.","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","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":"2","key":"11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00145-005-0357-6","article-title":"An improved real-quadratic-field-based key exchange procedure","volume":"19","author":"Jacobson, Michael J., Jr.","year":"2006","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"12","unstructured":"A.K. Lenstra and H.W. Lenstra, Jr., Algorithms in number theory, Tech. Report 87-008, University of Chicago, 1987."},{"key":"13","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":"14","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"},{"issue":"2","key":"15","first-page":"182","article-title":"Solving the Pell equation","volume":"49","author":"Lenstra, H. W., Jr.","year":"2002","journal-title":"Notices Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9920","issn-type":"print"},{"key":"16","unstructured":"P. L\u00e9vy, Sur le d\u00e9veloppement en fraction continue d\u2019un nombre choisi au hasard, Compositio Math. 3 (1936), 286\u2013303."},{"key":"17","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":"18","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1515\/crll.1985.361.50","article-title":"\u00dcber die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlk\u00f6rper","volume":"361","author":"Pohst, Michael","year":"1985","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"key":"19","first-page":"217","article-title":"The infrastructure of a real quadratic field and its applications","author":"Shanks, Daniel","year":"1972"},{"key":"20","isbn-type":"print","first-page":"163","article-title":"On Gauss and composition. I, II","author":"Shanks, Daniel","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0792301498"},{"key":"21","unstructured":"V. Shoup, NTL: A library for doing number theory, Software, 2001, Available from http:\/\/www.shoup.net\/ntl."},{"issue":"235","key":"22","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1090\/S0025-5718-00-01234-5","article-title":"Computer verification of the Ankeny-Artin-Chowla conjecture for all primes less than 100000000000","volume":"70","author":"van der Poorten, A. J.","year":"2001","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-45455-1_12","article-title":"An accelerated Buchmann algorithm for regulator computation in real quadratic fields","author":"Vollmer, Ulrich","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"issue":"154","key":"24","doi-asserted-by":"publisher","first-page":"593","DOI":"10.2307\/2007664","article-title":"A numerical investigation into the length of the period of the continued fraction expansion of \u221a\ud835\udc37","volume":"36","author":"Williams, H. C.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"25","isbn-type":"print","first-page":"397","article-title":"Solving the Pell equation","author":"Williams, H. C.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/1568811527"},{"issue":"177","key":"26","doi-asserted-by":"publisher","first-page":"405","DOI":"10.2307\/2007899","article-title":"On the parallel generation of the residues for the continued fraction factoring algorithm","volume":"48","author":"Williams, H. C.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01935-7\/S0025-5718-07-01935-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01935-7\/S0025-5718-07-01935-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:03:43Z","timestamp":1776783823000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01935-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,19]]},"references-count":26,"journal-issue":{"issue":"260","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["S0025-5718-07-01935-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-07-01935-7","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":[[2007,4,19]]}}}