Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-23T22:34:48.168Z Has data issue: false hasContentIssue false
  • English
  • Français

Subexponential class group and unit group computation in large degree number fields

Part of: Maps and general types of spaces defined by maps Representation theory of groups Linear function spaces and their duals Birational geometry

Published online by Cambridge University Press:  01 August 2014

Jean-François Biasse  and
Claus Fieker
Jean-François Biasse
Affiliation:
Computer Science Department and Mathematics Department, University of Calgary, 2500 University Drive NW, Calgary, Alberta T2N 1N4, Canada email biasse@lix.polytechnique.fr
Claus Fieker
Affiliation:
University of Kaiserslautern, Fachbereich Mathematik, Postfach 3049, 67653 Kaiserslautern, Germany email fieker@mathematik.uni-kl.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We describe how to compute the ideal class group and the unit group of an order in a number field in subexponential time. Our method relies on the generalized Riemann hypothesis and other usual heuristics concerning the smoothness of ideals. It applies to arbitrary classes of number fields, including those for which the degree goes to infinity.

MSC classification

Secondary: 54C40: Algebraic properties of function spaces 14E20: Coverings 46E25: Rings and algebras of continuous, differentiable or analytic functions 20C20: Modular representations and characters
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 385 - 403
Copyright
© The Author(s) 2014 

References

Adleman, L. and DeMarrais, J., ‘A subexponential algorithm for discrete logarithms over all finite fields’, Advances in cryptology — CRYPTO ’93, Proceedings of the 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22–26, 1993, Lecture Notes in Computer Science 773 (ed. Stinson, D.; Springer, 1993) 147–158.Google Scholar
Bach, E., ‘Explicit bounds for primality testing and related problems’, Math. Comp. 55 (1990) no. 191, 355–380.Google Scholar
Bach, E., ‘Improved approximations for Euler products’, Number theory, CMS Conference Proceedings 15 (American Mathematical Society, Providence, RI, 1995) 13–28.Google Scholar
Biasse, J.-F., ‘An L (1∕3) algorithm for ideal class group and regulator computation in certain number fields’, Math. Comp. 83 (2014) 2005–2031.CrossRefGoogle Scholar
Biasse, J.-F., ‘Subexponential time relations in large degree number fields’, Adv. Math. Commun. Preprint.Google Scholar
Biasse, J.-F., ‘Subexponential algorithms for number fields’, PhD Thesis, École Polytechnique, Paris, 2011.Google Scholar
Biasse, J.-F. and Fieker, C., ‘New techniques for computing the ideal class group and a system of fundamental units in number fields’, Comp. Res. Repository, Preprint, 2012, arXiv:1204.1294.Google Scholar
Bisson, G., ‘Endomorphism rings in cryptography’, PhD Thesis, LORIA, Nancy, France, 2011.Google Scholar
Buchmann, J., ‘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, Progress in Mathematics (ed. Goldstein, C.; Birkhäuser, Boston, 1990) 27–41.Google Scholar
Buchmann, J., Thiel, C. and Williams, H.C., ‘Short representation of quadratic integers’, Computational algebra and number theory, Mathematics and its Applications 325 (Springer, 1995) 159–185.Google Scholar
Cassels, J., An introduction to the geometry of numbers, Classics in Mathematics (Springer, 1997) ; corrected reprint of the 1971 edition.Google Scholar
Cohen, H., Diaz Y Diaz, F. and Olivier, M., ‘Subexponential algorithms for class group and unit computations’, J. Symbolic Comput. 24 (1997) no. 3–4, 433–441.CrossRefGoogle Scholar
Enge, A., Gaudry, P. and Thomé, E., ‘An L (1∕3) discrete logarithm algorithm for low degree curves’, J. Cryptology 24 (2011) no. 1, 24–41.CrossRefGoogle Scholar
Erdős, P. and Turán, P., ‘On some problems of a statistical group-theory. I.’, Z. Wahr. Verw. Geb. 4 (1965) 175–186.CrossRefGoogle Scholar
Gama, N. and Nguyen, P., ‘Finding short lattice vectors within Mordell’s inequality’, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17–20, 2008 (ed. Dwork, C.; ACM, 2008) 207–216.Google Scholar
Gordon, D., ‘Discrete logarithms in GF(p) using the number field sieve’, SIAM J. Discrete Math. 6 (1993) 124–138.CrossRefGoogle Scholar
Hafner, J.L. and McCurley, K.S., ‘A rigorous subexponential algorithm for computation of class groups’, J. Amer. Math. Soc. 2 (1989) 839–850.Google Scholar
Hanrot, G., Pujol, X. and Stehlé, D., ‘Analyzing blockwise lattice algorithms using dynamical systems’, Advances in Cryptology — CRYPTO 2011 — 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2011, Lecture Notes in Computer Science (ed. Rogaway, P.; Springer, 2011) 447–464.Google Scholar
Hanrot, G. and Stehlé, D., ‘Improved analysis of Kannan’s shortest lattice vector algorithm’, Advances in Cryptology — CRYPTO 2007, Lecture Notes in Computer Science 4622 (ed. Menezes, A.; Springer, 2007) 170–186.CrossRefGoogle Scholar
Jao, D. and Soukharev, V., ‘A subexponential algorithm for evaluating large degree isogenies’, Algorithmic number theory, Lecture Notes in Computer Science 6197 (eds Hanrot, G., Morain, F. and Thomé, E.; Springer, 2010) 219–233.CrossRefGoogle Scholar
Jenner, W.E., ‘On zeta functions of number fields’, Duke Math. J. 36 (1969) 669–671.CrossRefGoogle Scholar
Joux, A., Lercier, R., Smart, N. P. and Vercauteren, F., ‘The number field sieve in the medium prime case’, Advances in Cryptology — CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20–24, 2006, Lecture Notes in Computer Science 4117 (ed. Dwork, Cynthia; Springer, 2006) 326–344.CrossRefGoogle Scholar
Lenstra, A. K., Lenstra, H. W. Jr., Manasse, M. S. and Pollard, J. M., ‘The number field sieve’, STOC ’90: Proceedings of The Twenty-Second Annual ACM Symposium on Theory of Computing (ACM, New York, NY, 1990) 564–572.CrossRefGoogle Scholar
Lenstra, A.K., ‘On the calculation of regulators and class numbers of quadratic fields’, Journées Arithmétiques (Cambridge University Press, 1982) 123–150.Google Scholar
Micciancio, D. and Voulgaris, P., ‘A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations’, SIAM J. Comput. 42 (2013) no. 3, 1364–1391.CrossRefGoogle Scholar
Neukirch, J., Algebraic number theory, Comprehensive Studies in Mathematics (Springer, 1999).CrossRefGoogle Scholar
Novocin, A., Stehlé, D. and Villard, G., ‘An LLL-reduction algorithm with quasi-linear time complexity: Extended abstract’, Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11 (ACM, New York, NY, 2011) 403–412.CrossRefGoogle Scholar
Schnorr, C. P. and Euchner, M., ‘Lattice basis reduction: improved practical algorithms and solving subset sum problems’, Math. Program. 66 (1994) no. 2, 181–199.CrossRefGoogle Scholar
Schnorr, C.P., ‘A hierarchy of polynomial time lattice basis reduction algorithms’, Theor. Comput. Sci. 53 (1987) no. 2–3, 201–224.Google Scholar
Scourfield, E., ‘On ideals free of large prime factors’, J. Théor. Nombres Bordeaux 16 (2004) no. 3, 733–772.CrossRefGoogle Scholar
Shanks, D., ‘Class number, a theory of factorization, and genera’, Proceedings of Symposia in Pure Mathematics 20 (eds LeVeque, W. J. and Straus, E. G.; American Mathematical Society, 1969) 415–440.Google Scholar
Shanks, D., ‘The infrastructure of a real quadratic field and its applications’, Proceedings of the 1972 Number Theory Conference (American Mathematical Society, 1972) 217–224.Google Scholar
Smart, N. and Vercauteren, F., ‘Fully homomorphic encryption with relatively small key and ciphertext sizes’, Public Key Cryptography — PKC 2010, Lecture Notes in Computer Science 6056 (eds Nguyen, P. and Pointcheval, D.; Springer, 2010) 420–443.CrossRefGoogle Scholar
Storjohann, A., ‘Algorithms for matrix canonical forms’, PhD Thesis, Department of Computer Science, Swiss Federal Institute of Technology – ETH, 2000.Google Scholar
Thiel, C., On the complexity of some problems in algorithmic algebraic number theory, PhD Thesis, Universität des Saarlandes, 1995.Google Scholar