期刊
JOURNAL OF SYMBOLIC COMPUTATION
卷 121, 期 -, 页码 -出版社
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.jsc.2023.102261
关键词
Algebraic number field; LLL algorithm; Bareiss algorithm; Exact computation; Running time analysis
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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据