Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

An $ L(1/3)$ algorithm for ideal class group and regulator computation in certain number fields


Author: Jean-François Biasse
Journal: Math. Comp. 83 (2014), 2005-2031
MSC (2010): Primary 54C40, 14E20; Secondary 46E25, 20C20
DOI: https://doi.org/10.1090/S0025-5718-2014-02651-3
Published electronically: January 17, 2014
MathSciNet review: 3194139
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze the complexity of the computation of the class group structure, regulator, and a system of fundamental units of an order in a certain class of number fields. Our approach differs from Buchmann's, who proved a complexity bound under the generalized Riemann hypothesis of $ L(1/2,O(1))$ when the discriminant tends to infinity with fixed degree. We achieve a heuristic subexponential complexity in $ O(L(1/3,O(1)))$ under the generalized Riemann hypothesis when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thomé in the context of algebraic curves over finite fields. We also address rigorously the problem of the precision of the computation of the regulator.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 54C40, 14E20, 46E25, 20C20

Retrieve articles in all journals with MSC (2010): 54C40, 14E20, 46E25, 20C20


Additional Information

Jean-François Biasse
Affiliation: LIX, École Polytechnique, 91128 Palaiseau, France
Email: biasse@lix.polytechnique.fr

DOI: https://doi.org/10.1090/S0025-5718-2014-02651-3
Keywords: Number fields, ideal class group, regulator, units, index calculus, subexponentiality
Received by editor(s): December 17, 2009
Received by editor(s) in revised form: October 25, 2011
Published electronically: January 17, 2014
Additional Notes: The author was supported by a DGA grant
Article copyright: © Copyright 2014 American Mathematical Society