Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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


Authors: R. de Haan, M. J. Jacobson Jr. and H. C. Williams
Journal: Math. Comp. 76 (2007), 2139-2160
MSC (2000): Primary 11Y40; Secondary 11Y16
Published electronically: April 19, 2007
MathSciNet review: 2336288
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11Y16

Retrieve articles in all journals with MSC (2000): 11Y40, 11Y16


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

DOI: http://dx.doi.org/10.1090/S0025-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
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.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.