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

de Haan, R.; Jacobson, M., Jr.; Williams, H.

doi:10.1090/S0025-5718-07-01935-7

A fast, rigorous technique for computing the regulator of a real quadratic field
HTML articles powered by AMS MathViewer

by R. de Haan, M. J. Jacobson Jr. and H. C. Williams PDF

Math. Comp. 76 (2007), 2139-2160 Request permission

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 + \epsilon })$ 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.

References

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.
Johannes 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–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
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, 1990–91, Progr. Math., vol. 108, Birkhäuser Boston, Boston, MA, 1993, pp. 35–46 (French). MR 1263522
H. Cohen, F. Diaz y Diaz, and M. Olivier, Subexponential algorithms for class group and unit computations, J. Symbolic Comput. 24 (1997), no. 3-4, 433–441. Computational algebra and number theory (London, 1993). MR 1484490, DOI 10.1006/jsco.1996.0143
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.
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.
James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
Michael J. Jacobson Jr., Richard F. Lukes, and Hugh C. Williams, An investigation of bounds for the regulator of quadratic fields, Experiment. Math. 4 (1995), no. 3, 211–225. MR 1387478
M. J. Jacobson Jr., Á. Pintér, and P. G. Walsh, A computational approach for solving $y^2=1^k+2^k+\dots +x^k$, Math. Comp. 72 (2003), no. 244, 2099–2110. MR 1986826, DOI 10.1090/S0025-5718-03-01465-0
Michael J. Jacobson Jr., Renate Scheidler, and Hugh C. Williams, The efficiency and security of a real quadratic field based key exchange protocol, Public-key cryptography and computational number theory (Warsaw, 2000) de Gruyter, Berlin, 2001, pp. 89–112. MR 1881630
Michael J. Jacobson Jr., Renate Scheidler, and Hugh C. Williams, An improved real-quadratic-field-based key exchange procedure, J. Cryptology 19 (2006), no. 2, 211–239. MR 2213407, DOI 10.1007/s00145-005-0357-6
A.K. Lenstra and H.W. Lenstra, Jr., Algorithms in number theory, Tech. Report 87-008, University of Chicago, 1987.
A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178
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
H. W. Lenstra Jr., Solving the Pell equation, Notices Amer. Math. Soc. 49 (2002), no. 2, 182–192. MR 1875156
P. Lévy, Sur le développement en fraction continue d’un nombre choisi au hasard, Compositio Math. 3 (1936), 286–303.
Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
Michael Pohst and Hans Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkörper, J. Reine Angew. Math. 361 (1985), 50–72 (German). MR 807252, DOI 10.1515/crll.1985.361.50
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
Daniel Shanks, On Gauss and composition. I, II, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 163–178, 179–204. MR 1123074
V. Shoup, NTL: A library for doing number theory, Software , 2001, Available from http://www.shoup.net/ntl.
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$, Math. Comp. 70 (2001), no. 235, 1311–1328. MR 1709160, DOI 10.1090/S0025-5718-00-01234-5
Ulrich Vollmer, An accelerated Buchmann algorithm for regulator computation in real quadratic fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 148–162. MR 2041080, DOI 10.1007/3-540-45455-1_{1}2
H. C. Williams, A numerical investigation into the length of the period of the continued fraction expansion of $\sqrt {D}$, Math. Comp. 36 (1981), no. 154, 593–601. MR 606518, DOI 10.1090/S0025-5718-1981-0606518-7
H. C. Williams, Solving the Pell equation, Number theory for the millennium, III (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 397–435. MR 1956288
H. C. Williams and M. C. Wunderlich, On the parallel generation of the residues for the continued fraction factoring algorithm, Math. Comp. 48 (1987), no. 177, 405–423. MR 866124, DOI 10.1090/S0025-5718-1987-0866124-1