Back to Search
Start Over
Algebraic number fields and the LLL algorithm.
- Source :
-
Journal of Symbolic Computation . Mar2024, Vol. 121, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
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 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 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). [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGEBRAIC numbers
*ALGEBRAIC fields
*GAUSSIAN elimination
*ALGORITHMS
*ARITHMETIC
Subjects
Details
- Language :
- English
- ISSN :
- 07477171
- Volume :
- 121
- Database :
- Academic Search Index
- Journal :
- Journal of Symbolic Computation
- Publication Type :
- Academic Journal
- Accession number :
- 171393617
- Full Text :
- https://doi.org/10.1016/j.jsc.2023.102261