Mathematics of Computation

A fast, rigorous technique for computing the regulator of a real quadratic field

Author(s): R. de Haan; M. J. Jacobson Jr.; H. C. Williams.
Journal: Math. Comp. 76 (2007), 2139-2160.
MSC (2000): Primary 11Y40; Secondary 11Y16
Posted: April 19, 2007
Retrieve article in: PDF

Abstract: We present a new algorithm for computing the regulator of a real quadratic field $\mathbb{Q}(\sqrt{D}),$ based on an algorithm for unconditionally verifying the correctness of the regulator produced by a subexponential algorithm, that runs in expected time $O(D^{1/6 + \e})$ 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.

1.: C.S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl and des Regulators reellquadratischer Ordnungen, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany, 1994.
2.: J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres (Paris), 1988-89, pp. 27-41. MR 1104698 (92g:11125)
3.: H. Cohen, F. Diaz y Diaz, and M. Olivier, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel, Séminaire de Théorie des Nombres (Paris), 1993, pp. 35-46. MR 1263522 (94m:11151)
4.: -, Subexponential algorithms for class and unit group computations, Journal Symbolic Computation 24 (1997), 434-441. MR 1484490 (98m:11138)
5.: R. de Haan, A fast, rigorous technique for verifying the regulator of a real quadratic field, Master's thesis, Universiteit van Amsterdam, Amsterdam, May 2004.
6.: The LiDIA Group, LiDIA: a c++ library for computational number theory, Software, Technische Universität Darmstadt, Germany, 1997. See http://www.informatik.tu-darmstadt.de/TI/LiDIA.
7.: J.L. Hafner and K.S. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal American Mathematical Society 2 (1989), 837-850. MR 1002631 (91f:11090)
8.: M.J. Jacobson, Jr., R.F. Lukes, and H.C. Williams, An investigation of bounds for the regulator of quadratic fields, Experimental Mathematics 4 (1995), no. 3, 211-225. MR 1387478 (97d:11173)
9.: M.J. Jacobson, Jr., Á. Pintér, and P.G. Walsh, A computational approach for solving $y^2 = 1^k +2^k+\cdots + x^k$ , Mathematics of Computation 72 (2003), no. 244, 2099-2110. MR 1986826 (2004c:11241)
10.: M.J. Jacobson, Jr., R. Scheidler, and H.C. Williams, The efficiency and security of a real quadratic field based key exchange protocol, Public Key Cryptography and Computational Number Theory, Walter de Gruyter, Warsaw, 2001, pp. 89-112. MR 1881630 (2003f:94062)
11.: -, An improved real quadratic field based-key exchange procedure, Journal of Cryptology 19 (2006), 211-239. MR 2213407 (2006k:94089)
12.: A.K. Lenstra and H.W. Lenstra, Jr., Algorithms in number theory, Tech. Report 87-008, University of Chicago, 1987.
13.: -, Algorithms in number theory, Handbook of theoretical computer science A (1990), 673-715. MR 1127178
14.: H.W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, London Mathematical Society Lecture Notes Series 56 (1982), 123-150. MR 0697260 (86g:11080)
15.: -, Solving the pell equation, Notices of the American Mathematical Society 49 (2002), no. 2, 182-192. MR 1875156 (2002i:11028)
16.: P. Lévy, Sur le développement en fraction continue d'un nombre choisi au hasard, Compositio Math. 3 (1936), 286-303.
17.: K.S. McCurley, Cryptographic key distribution and computation in class groups, Proceedings NATO ASI on Number Theory and Applications (Dordrecht), ASI series C, vol. 265, Kluwer, 1989, pp. 459-479. MR 1123090 (92e:11149)
18.: M. Pohst and H. Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkörper, J. reine angew. Math. 361 (1985), 50-72. MR 0807252 (87g:11147)
19.: D. Shanks, The infrastructure of a real quadratic field and its applications, Proceedings 1972 Number Theory Conference (Boulder), 1972. MR 0389842 (52:10672)
20.: -, On Gauss and composition, Number Theory and Applications (NATO-Advanced Study Institute, Banff, 1988) (R.A. Mollin, ed.), Kluwer Academic Publishers Dordrecht, 1989, pp. 163-204. MR 1123074 (92e:11150)
21.: V. Shoup, NTL: A library for doing number theory, Software, 2001, Available from http://www.shoup.net/ntl.
22.: A.J van der Poorten, H.J.J. te Riele, and H.C. Williams, Computer verification of the Ankeny-Artin-Chowla conjecture for all primes less than 100 000 000 000, Mathematics of Computation 70 (2000), no. 235, 1311-1328. MR 1709160 (2001j:11125)
23.: U. Vollmer, An accelerated Buchmann algorithm for regulator computation in real quadratic fields, Algebraic Number Theory (Sydney, Australia), July 2002, pp. 148-162. MR 2041080 (2005d:11184)
24.: H.C. Williams, A numerical investigation into the length of the period of the continued fraction expansion of $\sqrt{D}$ , Mathematics of Computation 36 (1981), 593-601. MR 0606518 (82f:10011)
25.: -, Solving the Pell equation, Proceedings Millennial Conference on Number Theory (A.K. Peters, ed.), Natick MA, 2002, pp. 397-435. MR 1956288 (2003m:11051)
26.: H.C. Williams and M.C. Wunderlich, On the parallel generation of the residues for the continued fraction algorithm, Mathematics of Computation 48 (1987), no. 177, 405-423. MR 0866124 (88i:11099)

R. de Haan
Affiliation: Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Address at time of publication: Centrum voor Wiskunde en Informatica, Kruislaan 413, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
Email: R.de.Haan@cwi.nl

M. J. Jacobson Jr.
Affiliation: Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: jacobs@cpsc.ucalgary.ca

H. C. Williams
Affiliation: Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: williams@math.ucalgary.ca

DOI: 10.1090/S0025-5718-07-01935-7
PII: S 0025-5718(07)01935-7
Keywords: Regulator computation, regulator verification, real quadratic number fields, reduced principal ideals, $(f,p)$ representations
Received by editor(s): May 23, 2005
Posted: April 19, 2007
Additional Notes: The second author's research is supported by NSERC of Canada
The third author's research is supported by NSERC of Canada and iCORE of Alberta.
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS