Algebraic number fields and the LLL algorithm

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 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 Zn to Kn, and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). (c) 2023 Elsevier Ltd. All rights reserved.

Automated summary

This paper analyzes the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. It provides running time and output size calculations for operations in the number field, and extends the algorithms to handle operations in a specific type of number field. The paper also gives a polynomial upper bound on the running time when computations are performed exactly.