×

Algebraic number fields and the LLL algorithm. (English) Zbl 1539.11154

Summary: In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let \(K\) be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in \(K\) in terms of the size of the input and the parameters of \(K\). We include some earlier results about these, but we go further than them, e.g. we also analyze some \(\mathbb{R} \)-specific operations in \(K\) like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from \(\mathbb{Z}^n\) to \(K^n\), and give a polynomial upper bound on the running time when the computations in \(K\) are performed exactly (as opposed to floating-point approximations).

MSC:

11Y40 Algebraic number theory computations
68W30 Symbolic computation and algebraic computation
11R99 Algebraic number theory: global fields

References:

[1] Bareiss, E. H., Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comput., 22, 565-578 (1968) · Zbl 0187.09701
[2] Belabas, K., Topics in computational algebraic number theory, J. Théor. Nr. Bordx., 16, 19-63 (2004) · Zbl 1078.11071
[3] Biasse, J.-F.; Fieker, C.; Hofmann, T., On the computation of the HNF of a module over the ring of integers of a number field, J. Symb. Comput., 80, 581-615 (2017) · Zbl 1403.11084
[4] Cassels, J. W.S., An Introduction to the Geometry of Numbers (1997), Springer-Verlag Berlin Heidelberg · Zbl 0866.11041
[5] Cohen, H., A Course in Computational Algebraic Number Theory (1996), Springer-Verlag Berlin Heidelberg
[6] Fieker, C.; Stehlé, D., Short bases of lattices over number fields, (Hanrot, G.; Morain, F.; Thomé, E., Algorithmic Number Theory, 9th International Symposium, Proceedings, vol. 6197 (2010)), 157-173 · Zbl 1260.11084
[7] Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithms for Computer Algebra (1992), Kluwer Academic Publishers · Zbl 0805.68072
[8] Knuth, D. E., The Art of Computer Programming, vol. 2 (1998), Addison-Wesley · Zbl 0895.65001
[9] Lee, C.; Pellet-Mary, A.; Stehlé, D.; Wallet, A., An LLL algorithm for module lattices, (Advances in Cryptology, ASIACRYPT (2019)), 59-90 · Zbl 1455.94178
[10] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[11] Morel, I.; Stehlé, D.; Villard, G., H-LLL: using Householder inside LLL, (Proceedings of ISSAC (2009)), 271-278 · Zbl 1237.65041
[12] Nguyen, P. Q.; Stehlé, D., An LLL algorithm with quadratic complexity, SIAM J. Comput., 39, 874-903 (2009) · Zbl 1214.11139
[13] Pethő, A.; Pohst, M. E.; Bertók, Cs., On multidimensional Diophantine approximation of algebraic numbers, J. Number Theory, 171, 422-448 (2017) · Zbl 1419.11097
[14] Plantard, T.; Susilo, W.; Zhang, Z., Adaptive precision floating point LLL, (Boyd, C.; Simpson, L., Information Security and Privacy, ACISP 2013. Information Security and Privacy, ACISP 2013, Lecture Notes in Computer Science, vol. 7959 (2013)), 104-117 · Zbl 1316.11115
[15] Pohst, M.; Zassenhaus, H., Algorithmic Algebraic Number Theory (1997), Cambridge University Press · Zbl 0685.12001
[16] Saruchi; Morel, I.; Stehlé, D.; Villard, G., LLL reducing with the most significant bits, (ISSAC. ISSAC, Kobe, Japan (2014)), 367-374 · Zbl 1325.68298
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.