Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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
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?)

  • 1. L.M. Adleman, J. DeMarrais, and M.-D. Huang.
    A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields.
    In Leonard M. Adleman and Ming-Deh Huang, editors, Algorithmic Number Theory, volume 877 of Lecture Notes in Computer Science, pages 28-40, Berlin, 1994. Springer-Verlag. MR 1322708 (96b:11078)
  • 2. E. Bach.
    Explicit bounds for primality testing and related problems.
    Mathematics of Computation, 55(191):355-380, 1990. MR 1023756 (91m:11096)
  • 3. E. Bach.
    Improved approximations for Euler products.
    Journal of the American Mathematical Society, 15:13-28, 1995. MR 1353917 (96i:11124)
  • 4. R.P. Brent.
    Fast multiple-precision evaluation of elementary functions.
    Journal of the ACM, 23:242-251, 1976. MR 0395314 (52:16111)
  • 5. J. Buchmann.
    A subexponential algorithm for the determination of class groups and regulators of algebraic number fields.
    In Catherine Goldstein, editor, Séminaire de Théorie des Nombres, Paris 1988-1989, Progress in Mathematics, pages 27-41, Boston, 1990. Birkhäuser. MR 1104698 (92g:11125)
  • 6. E.R. Canfield, P. Erdős, and C. Pomerance.
    On a problem of Oppenheim concerning `factorisatio numerorum'.
    J. Number Theory, 17:1-28, 1983. MR 712964 (85j:11012)
  • 7. A.L. Chistov.
    The complexity of constructing the ring of integers of a global field.
    Dokl. Akad. Nauk SSSR 306 (1989), 1063-1067.
    English translation.
    Soviet Math. Dokl., (1989), 597-600. MR 1014763 (90g:11170)
  • 8. H. Cohen.
    A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics.
    Springer-Verlag, 1991. MR 1228206 (94i:11105)
  • 9. H. Cohen.
  • 10. A. Enge.
    Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time.
    Mathematics of Computation, 71:729-742, 2001. MR 1885624 (2003b:68083)
  • 11. A. Enge, P. Gaudry and E. Thomé.
    An $ {L}(1/3)$ discrete logarithm algorithm for low degree curves.
    Journal of Cryptology 24(1):24-41, 2011. MR 2755161 (2011m:11241)
  • 12. C. Fieker and M. Pohst.
    Dependency of units in number fields.
    Mathematics of Computation, 75:1507-1518, 2006. MR 2219041 (2007a:11168)
  • 13. M. Giesbrecht, M. Jacobson, and A. Storjohann.
    Algorithms for large integer matrix problems.
    In S. Boztas and I. Shparlinski, editors, Proceedings of the 14th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-14, volume 2227 of Lecture Notes in Computer Science, pages 297-307, Heidelberg, 2001. Springer-Verlag. MR 1913476 (2003i:15016)
  • 14. J.L. Hafner and K.S. McCurley.
    A rigorous subexponential algorithm for computation of class groups.
    Journal of American Society, 2:839-850, 1989. MR 1002631 (91f:11090)
  • 15. M. Jacobson and H.C. Williams.
    Solving the Pell equation.
    CMS Books in Mathematics. Springer-Verlag, 2009. MR 2466979 (2009i:11003)
  • 16. E. Kaltofen. and G. Villard
    On the complexity of computing determinants.
    Computational Complexity, 13:91-130, 2005. MR 2120701 (2005m:68263)
  • 17. H.W. Lenstra, Jr.
    On the calculation of regulators and class numbers of quadratic fields.
    In Journées Arithmétiques, pages 123-150. Cambridge Univ. Press, 1982. MR 697260 (86g:11080)
  • 18. M. Mignotte.
    An inequality about factors of polynomials.
    Mathematics of Computation, 28:1153-1157, 1974. MR 0354624 (50:7102)
  • 19. S. Neukirch.
    Algebraic number theory.
    Comprehensive Studies in Mathematics. Springer-Verlag, 1999.
    ISBN 3-540-65399-6. MR 1697859 (2000m:11104)
  • 20. S. Pauli and J. Klüners.
    Computing residue class rings and Picard groups of orders.
    Journal of Algebra, 292:47-64, 2005. MR 2166795 (2006f:11142)
  • 21. J.B. Rosser and L. Schoenfeld.
    Approximate formulas for some functions of prime numbers.
    Illinois Journal of Mathematics, 6:64-94, 1962. MR 0137689 (25:1139)
  • 22. M. Seysen.
    A probabilistic factorization algorithm with quadratic forms of negative discriminant.
    Mathematics of computation, 48:757-780, 1987. MR 878705 (88d:11129)
  • 23. D. Shanks.
    Class number, a theory of factorization, and genera.
    In W.J. LeVeque and E.G. Straus, editors, Proceedings of Symposia in Pure Mathematics, volume 20, pages 415-440. American Mathematical Society, 1969. MR 0316385 (47:4932)
  • 24. D. Shanks.
    The infrastructure of a real quadratic field and its applications.
    In Proceedings of the 1972 Number Theory Conference, pages 217-224. Boulder: University of Colorado, 1972. MR 0389842 (52:10672)
  • 25. C. L. Siegel.
    Über die Classenzahl quadratischer Zahlkörper.
    Acta Arithmetica, 1:83-86, 1935.
  • 26. A. Storjohann.
    Algorithms for Matrix Canonical Forms.
    PhD thesis, Department of Computer Science, Swiss Federal Institute of Technology - ETH, 2000.
  • 27. U. Vollmer.
    A note on the Hermite basis computation of large integer matrices.
    In J. Rafael Sendra, editor, International Symposium on Symbolic and Algebraic Computation, ISSAC '03, pages 255-257. ACM Press, 2003. MR 2035220
  • 28. X. Wang and V. Pan.
    Acceleration of euclidean algorithm and rational number reconstruction.
    SIAM J. Comput., 32(2):548-556, 2003. MR 1969404 (2004a:68173)

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

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

American Mathematical Society