×

An \(L(1/3)\) algorithm for ideal class group and regulator computation in certain number fields. (English) Zbl 1346.11065

The author develops a new algorithm for the computation of ideal class groups \(Cl\) and regulators \(R\) in certain families of number fields \(F\). He analyzes the expected computation times when both, the degree and the absolute value of the discriminant of \(F\), tend to infinity. Previous results by J. A. Buchmann et al. [Eurocrypt 1989, Lect. Notes Comput. Sci. 434, 597–6169 (1990; Zbl 0734.68047)] were proven for fixed degree and growing discriminants but arbitrary number fields. The complexity of Buchmann’s algorithm was \(L(1/2)\).
The methods for the calculation of the class group and the regulator follow the precedent of Buchmann inasmuch as Biasse makes use of a factor basis of ideals and relations among those. The major difference to Buchmann is that he cannot use random relations since they yield ideals which would still need to be reduced. But for a sufficiently small estimate of the running time of the reduction procedure the field degree must stay bounded. Instead Biasse applies an algorithm of A. Enge et al. [J. Cryptology 24, No. 1, 24–41 (2011; Zbl 1208.94042)] which those authors developed for calculating the group structure of the Jacobian for a certain class of curves. A careful analysis shows that Biasse’s algorithm is in the class \(L(1/3)\).
Analogous to Buchmann his result requires the assumption of GRH. Additionally, he needs two more heuristic assumptions concerning the smoothness of principal ideals and the number of necessary relations for proving his result. Biasse also presents an infinite family of number fields which satisfy the prerequisites for the estimate of the running time of the new algorithm.

MSC:

11Y16 Number-theoretic algorithms; complexity
11Y40 Algebraic number theory computations
11R29 Class numbers, class groups, discriminants
11R27 Units and factorization

Software:

PARI/GP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0829.11068 · doi:10.1007/3-540-58691-1_39
[2] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355 – 380. · Zbl 0701.11075
[3] 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. · Zbl 0842.11046
[4] Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242 – 251. · Zbl 0324.65018 · doi:10.1145/321941.321944
[5] 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.
[6] 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. · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1
[7] 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.
[8] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[9] H. Cohen. Pari. http://pari.math.u-bordeaux.fr/
[10] Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), no. 238, 729 – 742. · Zbl 0988.68069
[11] Andreas Enge, Pierrick Gaudry, and Emmanuel Thomé, An \?(1/3) discrete logarithm algorithm for low degree curves, J. Cryptology 24 (2011), no. 1, 24 – 41. · Zbl 1208.94042 · doi:10.1007/s00145-010-9057-y
[12] Claus Fieker and Michael E. Pohst, Dependency of units in number fields, Math. Comp. 75 (2006), no. 255, 1507 – 1518. · Zbl 1097.11061
[13] 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. · Zbl 1056.11078 · doi:10.1007/3-540-45624-4_31
[14] 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. · Zbl 0702.11088
[15] 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. · Zbl 1177.11027
[16] Erich Kaltofen and Gilles Villard, On the complexity of computing determinants, Comput. Complexity 13 (2004), no. 3-4, 91 – 130. · Zbl 1061.68185 · doi:10.1007/s00037-004-0185-3
[17] 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.
[18] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153 – 1157. · Zbl 0299.12101
[19] 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. · Zbl 0956.11021
[20] Jürgen Klüners and Sebastian Pauli, Computing residue class rings and Picard groups of orders, J. Algebra 292 (2005), no. 1, 47 – 64. · Zbl 1094.11046 · doi:10.1016/j.jalgebra.2005.04.013
[21] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64 – 94. · Zbl 0122.05001
[22] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757 – 780. · Zbl 0619.10004
[23] 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.
[24] 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. · Zbl 0334.12005
[25] C. L. Siegel. Über die Classenzahl quadratischer Zahlkörper. Acta Arithmetica, 1:83-86, 1935. · JFM 61.0170.02
[26] A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, Department of Computer Science, Swiss Federal Institute of Technology - ETH, 2000.
[27] 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. · Zbl 1072.68701 · doi:10.1145/860854.860905
[28] Xinmao Wang and Victor Y. Pan, Acceleration of Euclidean algorithm and rational number reconstruction, SIAM J. Comput. 32 (2003), no. 2, 548 – 556. · Zbl 1031.68149 · doi:10.1137/S0097539702408636
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.