Algebraic number fields and the LLL algorithm

DOI10.1016/J.JSC.2023.102261MaRDI QIDQ6051125zbMATH OpenOpenAlexFDO

Authors Marcell János Uray

Publication date 19 September 2023

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.01634

zbMATH Keywords

algebraic number fieldexact computationLLL algorithmrunning time analysisBareiss algorithm

Mathematics Subject Classification ID

Algebraic numbers; rings of algebraic integers (11R04) Algebraic number theory computations (11Y40)

Abstract: 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 $mathbbR$-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).

Recommendations

• An LLL algorithm with quadratic complexity
• On validated computing in algebraic number fields
• scientific article; zbMATH DE number 1113832
• scientific article; zbMATH DE number 17811
• Floating-Point LLL Revisited

Cites work

• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 194764 (Why is no real title available?)
• Adaptive precision floating point LLL
• An LLL algorithm for module lattices
• An LLL algorithm with quadratic complexity
• An introduction to the geometry of numbers.
• Factoring polynomials with rational coefficients
• H-LLL: using Householder inside LLL
• LLL reducing with the most significant bits
• On multidimensional Diophantine approximation of algebraic numbers
• On the computation of the HNF of a module over the ring of integers of a number field
• Short bases of lattices over number fields
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Topics in computational algebraic number theory

This page was built for publication: Algebraic number fields and the LLL algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6051125)