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
Additional Information
- 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
- Received by editor(s): May 23, 2005
- Published electronically: 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 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 2139-2160
- MSC (2000): Primary 11Y40; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-07-01935-7
- MathSciNet review: 2336288