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

Biasse, Jean-François

doi:10.1090/S0025-5718-2014-02651-3

An $L(1/3)$ algorithm for ideal class group and regulator computation in certain number fields
HTML articles powered by AMS MathViewer

by Jean-François Biasse PDF

Math. Comp. 83 (2014), 2005-2031 Request permission

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

Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 28–40. MR 1322708, DOI 10.1007/3-540-58691-1_{3}9
Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13–28. MR 1353917, DOI 10.1016/0009-2614(95)01161-4
Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944
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
E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), no. 5, 1063–1067 (Russian); English transl., Soviet Math. Dokl. 39 (1989), no. 3, 597–600. MR 1014763
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
H. Cohen. Pari. http://pari.math.u-bordeaux.fr/
Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), no. 238, 729–742. MR 1885624, DOI 10.1090/S0025-5718-01-01363-1
Andreas Enge, Pierrick Gaudry, and Emmanuel Thomé, An $L(1/3)$ discrete logarithm algorithm for low degree curves, J. Cryptology 24 (2011), no. 1, 24–41. MR 2755161, DOI 10.1007/s00145-010-9057-y
Claus Fieker and Michael E. Pohst, Dependency of units in number fields, Math. Comp. 75 (2006), no. 255, 1507–1518. MR 2219041, DOI 10.1090/S0025-5718-06-01899-0
Mark Giesbrecht, Michael Jacobson Jr., and Arne Storjohann, Algorithms for large integer matrix problems, Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001) Lecture Notes in Comput. Sci., vol. 2227, Springer, Berlin, 2001, pp. 297–307. MR 1913476, DOI 10.1007/3-540-45624-4_{3}1
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. and Hugh C. Williams, Solving the Pell equation, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2009. MR 2466979, DOI 10.1007/978-0-387-84923-2
Erich Kaltofen and Gilles Villard, On the complexity of computing determinants, Comput. Complexity 13 (2004), no. 3-4, 91–130. MR 2120701, DOI 10.1007/s00037-004-0185-3
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
M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI 10.1090/S0025-5718-1974-0354624-3
Jürgen Neukirch, Algebraic number theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. MR 1697859, DOI 10.1007/978-3-662-03983-0
Jürgen Klüners and Sebastian Pauli, Computing residue class rings and Picard groups of orders, J. Algebra 292 (2005), no. 1, 47–64. MR 2166795, DOI 10.1016/j.jalgebra.2005.04.013
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI 10.1090/S0025-5718-1987-0878705-X
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
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
C. L. Siegel. Über die Classenzahl quadratischer Zahlkörper. Acta Arithmetica, 1:83–86, 1935.
A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, Department of Computer Science, Swiss Federal Institute of Technology – ETH, 2000.
Ulrich Vollmer, A note on the Hermite basis computation of large integer matrices, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2003, pp. 255–257. MR 2035220, DOI 10.1145/860854.860905
Xinmao Wang and Victor Y. Pan, Acceleration of Euclidean algorithm and rational number reconstruction, SIAM J. Comput. 32 (2003), no. 2, 548–556. MR 1969404, DOI 10.1137/S0097539702408636